The ICSP header is in the same relative place on the UNO and MEGA. It is the only place where the SPI interface (Uno 11, 12, 13, Mega 50, 51, 52) are in the same physical location on both boards. That's why shields that use SPI have to use the ICSP header if they want to work on both boards.
The shield documentation says that the SD slot CS/SS line is connected to Pin 4 on the Arduino. Did you tell the SD library to use Pin 4?