Memory chip for arduino
You can quite easily connect multiple 128kB SPI ram chips to an Arduino. 4 of them together would give you 512kB of extra SPI-connected SRAM.

Access isn't super fast.

Another option is to use a parallel 8-bit SRAM chip. These take a lot more wiring since you need 8 wires for the data, log2(n) wires for the address, plus a couple of control wires (OE, WE, etc). But if you wire it making use of entire IO ports you can get much faster access times.  Also, these come in larger capacities than the SPI SRAM chips.

There is also PSRAM available in even bigger capacities. The same interface as SRAM but it's actually DRAM. The "P" stands for "Pseudo". You can get these in megabyte capacities, although they are usually in a BGA footprint, so you'd need to find one on a breakout board.