I ran the attached sketch, modified to use Pins 10 & 11 (with Softserial) for about 40 minutes now and still don't get any GPS data on the Serial Monitor.
Post a picture of how the GPS IS connected.
Stop using SoftwareSerial when you have 4 hardware serial ports on the Mega.