I would have thought that anything over 64K won't run because it is an 8 bit processor and so it has a 16 bit absolute address field. That only leaves you with 64K to play in.
I do belive the large AVR chips can address much more then 64kB of program memory. The AVR Mega1280 has 128kB of flash and some go to 256kB I think. The GCC compiler uses sepecial instructions for accessing the larger flash memory on those chips that have extended program space.
Recall that the AVR chips use a Harvard design where the program memory is separate from data memory and hence can and is of a different buss width as well as length.