Ein paar Anmerkungen:
Ich würde auch ein TTL-Modul nehmen, idealerweise mit der gleichen Versorgungsspannung wie der Controller.
Die Datenmenge kann man so nicht abschätzen. Welche Daten und wie oft soll gespeichert werden?
In Bits brauchst du nichts zerlegen, Bytes reichen
Die meisten GPS-Module liefern nur eine Messung pro Sekunde, einige gehen bis 5 x pro Sekunde hoch.
Je mehr du mit den Daten anstellen willst, desto schneller sollte die serielle Übertragung sein (billige Module können u.U. nur 4800/9600 baud)
Selbst mit meiner C-Control kann ich GPS-Daten locker loggen. Der Mega wird unterfordert
Nimm auf jeden Fall ein GPS-Modul mit anständiger Dokumentation und nicht eine billige GPS-Maus.
Zur Übersicht kannst du mal bei sparkfun schauen.

Viel Spaß damit

Stefan