You might extend the RAM of the MEGA with FRAM - Adafruit I2C Non-Volatile FRAM Breakout - 256Kbit / 32KByte : ID 1895 : $9.95 : Adafruit Industries, Unique & fun DIY electronics and kits
OK, performance will be less than you want but it works, and you can tweak the I2C to at least 600KHz
Check - https://github.com/RobTillaart/Arduino/tree/master/libraries/FRAM