My first thought was to have the Mega directly connected to the eeprom address/data/control lines. When it received an address it would then lookup the corresponding data byte in it's own flash memory and put it on the data bus.

A closer look at the timing charts for both chips shows that this approach will be too slow even with highly optimised AVR assembly language routines - which I wasn't going to attempt I had hope to do everything from within the Arduino IDE!