The datasheet link seams broken, if its a parallel interface EEPROM then don't suggest using it because your gonna need hell a lot of pins. As Nigel suggested yes try a SD card. Microchip gives you a FAT lib that has a built in interface to a SD card. Its incredibly easy to get working and will give you up to 4GB or even more if you use a IDE hard drive with FAT32. I sugest you stick to a SD card tho.Its low power, small,only 4 pins to interface,cheap and your most probably not even going need 128MB.The smallest cards you find in the stores are nowadays 512MB and are dirt cheap.
But if you want to try getting it to work feel free to do so.