Did it work at 16MHz? It should have.
I tried with 8 MHz and it worked fine. Tried again with 1 MHz and it returned:
$@} °202020î000,2424 0860,p"îúúr2608,,0,8,0î88,8>0î2,L r0,M‰H²žzú$@=ô
°202020î000,@Iˆ’ºÎ²úb‚¿04808î2618,
Tried at 1 MHz with UART3 and the data was fine. I guess AltSoftSerial can't deal with 9600bps at 1 MHz 
I took off the rest of the sentences just leaving GPRMC and GPGGA and now it works perfectly for both 19200 and 38400 with UART3! I guess the problem was being caused by the Serial buffer or maybe the GPS and the MEGA lose sync after some time continually transmitting/receiving data. I will try it now with SoftwareSerial and AltSoftSerial.
@edit I tried AltSoftSerial and SoftwareSerial for 19200 and 38400. Both worked for AltSoftSerial. The GPRMC messages were being cut using SoftwareSerial.
Did you try it with timer 0 disabled?
AltSoftSerial is great because it doesn't tie up the processor the way SoftwareSerial does. But the tradeoff is that its ISR has to be entered multiple times per character (not every bit though). At 16MHz, an ISR() that does nothing takes a minimum of about 2.6us. At 1MHz the minimum is 42us. But of course an ISR will also execute user code. I don't know what the longest path is through the AltSoftSerial ISRs. But in the worst case the ISR would be invoked on successive bits AND there would be a timer 0 overflow interrupt in between. It's hard to imagine that wouldn't be a problem. And at 9600 baud you're guaranteed to get a timer 0 interrupt with every character. I don't know why I suggested you try it! 
So at that clock speed maybe the SoftwareSerial approach is the only one that would work. Or even just sitting in a dedicated loop in your sketch, interrupts disabled, until the entire GPS report has been received and saved in a big buffer.
Just to add that this thread pointed me in the right directions for the similar problems I was seeing. I have an AtTiny85V that I am running SoftwareSerial on to receive text to display from a serially connected Raspberry Pi (via GPIO pins). The AtTiny85V is also using TinyWireM and an LCD library to drive an I2C LCD. (The Pi could drive the LCD direct, but is via the AtTiny85 so that info can be shown on LCD during Pi boot up and after shutdown). The Serially received text was occasionally displaying garbled on the LCD, only some of the time. The clue about interrupt based time being too short at the standard 9600 baud on a 1Mhz tiny rang true. The i2C lCD seemed always correct as i2c had a clock
Line and data line, so stretching of time has no effect. Serial listening to a master Pi with no clock needs good timing though. I changed the AtTiny85V to 8Mhz from 1MHz (after updating the fuses via boot loader first, keeping serial comms at 9600 baud, and the garbling disappeared.