Craig,

my current project uses 2Mb of video RAM + 2Mb of temporal memory. Both segments each use four 256kbit x 16 Samsung K6R4016 fast SRAM addressed via CPLD Altera ACEX. Vendor realizes the die with different bus width including 8-bit data bus wide - the part is called K6R4008C1D (for 5V).
Indeed, you will be need with CPLD or extra port/latch to select highest address byte (or its decoding). Access time for the part is fast enough, let say it is 8..10ns, which is compatible with the fastest 8051-like devices (we use SiLabs C8051F120 at 98MHz here).
The SRAM is available in both SOJ and TSOP2 packages.

The limitations are:
- chip is "only" 512 kbytes;
- due fast speed it "eats" 80mA in active state;
- the cost is about 2..3USD.

Regards,
Oleg