Cheap 2-5mb memory to use with arduino
I assume that, if this is a cost sensitive item, you need a reliable supply of multiples (so looking for small SD cards on e-bay isn't a viable solution).

Does it need to be non-volatile storage? If it does't you may be able to find small 8-bit wide RAM chips at a pretty good price. If it needs to be non-volatile, you might look at individual flash chips. I found this one, an 8-bit by 512 KB Serial-SPI flash chip for £0.19 (about $0.28 US) in single units and £0.176 if you can by 100 at a time. I would expect DRAM chips and chips with a simpler interface to be less expensive (but you might end up spending more on interfacing the chips so it might end up as a wash).

If you're able to consider a variety of processor chips it might be worth looking for something that has adequate storage on chip. That might be the most cost effective way to get the space.