Thanx, I understand what you're saying (and what PaulS said), but how do I configure the Arduino to get the data in on pins 16 & 17?
I'm not trying to be unkind, but I don't think you are understanding what PaulS and I are saying. I don't have a Mega, but aren't pins 16 & 17 Serial2? Access Serial2 just like any other serial device.
Looking at other GPS libraries, I see some use "Adafruit_GPS GPS(&Serial2);" to tell the Arduino where the GPS data comes from.
But the difference here is TinyGPS doesn't access any external ports. You have to do that yourself in your code. So you would do a Serial2.read() to a buffer variable (datatype char or larger) and then pass that variable to TinyGPS's method .encode(). Keep doing this until the .encode() method returns a true. You have to do the communication with the GPS device yourself in your sketch. I suppose you could skip the buffer variable entirely by putting the serial read inside the method, but then it would probably be best to use a flag variable for the return of the encode method.
Something like (untested code here, I have neither a Mega nor a GPS shield):
#include <TinyGPS.h>
TinyGPS gps;
boolean validGPS = false;
void setup()
{
Serial2.begin(9600); // or what ever the GPS's baudrate is
}
void loop()
{
if (Serial2.available())
{
validGPS = gps.encode(Serial2.read());
}
if (validGPS)
{
// TinyGPS has told us we have received a valid GPS fix. We can now query it for position/course/time/etc. information.
}
}
Note, even with a good GPS fix, it will take several loops through loop() to fetch a full NMEA sentence. This is good because it allows the sketch to do OtherThings
tm while it waits for GPS fix. An example of non-blocking code.

I'm using a SIM900 GSM shield on Serial1, and had to "hard code" the Serial1 interface in the GSM.cpp file. The developer has given some clear instructions on how to do that, but I can't figure out how to do something similar with TinyGPS.
I'm using a MEGA 2560, with a Adafruit Ultimate GPS breakout V3 on Serial2, and a IComsat GMS shield on Serial1
As long as the GPS unit on the Adafruit breakout sends standard $GPRMC and/or $GPGGA sentences, it should work with TinyGPS. (I expect that it does, but may need some configuration first. I really don't know it's default state.)
Don't forget to test where the GPS can actually get a fix. TinyGPS ignores NMEA sentences that don't indicate a fix. (i.e. even if the NMEA sentence is properly formed, if the GPS is reporting in those sentences that there is no GPS fix then TinyGPS will ignore that sentence. If it's important to your project, don't forget to keep an eye on fix_age.