I've found a few TSOP56 devices, all of them have much much more capacity than this one. So I wasn't sure if they would work.
You have to realise capacity is only there if it is addressed.
If the device never addresses beyond the 16Mbit or whatever that device is, then you can fit a 64Mbit part and it'll behave just like a 16Mbit one, provided you program it with the same image. The CPU will not know or care that such a large device is fitted.
You could have issues if the additional address lines aren't grounded, so you may have to check a schematic (if available) or meter out signals to see if they go to the CPU. In my experience it's pretty common for engineers to connect all of the address lines of their flash chip to the processor, because they may not know in advance what size they want to fit. However, this isn't guaranteed. If you're steady with soldering you could connect the redundant address lines to ground and program the image into the zero page of the flash.