A bit of research shows how little I know and how quickly I can be confused!
I built a little program for the Arduino Mega and dumped the assembly. Code and data pointers all appear to be 16 bit. It appears 16 bit pointers are used for small programs built for the Mega.
The Wikipedia articles claim that code pointers are 24 bits for the Mega processor. There is an implication that data pointers are still 16 bit.
The Atmel documentation describes several new registers that are used to extend addresses past 16 bits. The new registers appear to provide access to a "window" of memory. Some of the instructions (like CALL) appear to work on word boundaries so they may be able to access the full 128K without a "window" register. Even on the Mega processor, the instruction set appears to favor the first 64K (or a 64K window; I can't tell for certain).
Ugh! Right now I'm VERY grateful to have a C++ compiler that hides those details!