I might just have a poor imagination, but I can't imagine a case where 65536 formula are needed to solve any particular problem. In large sheets like these there is often a lot of "history" which is calculated but never changes.
If you need to speed up your worksheet, try to find some calculations that will never calculate anything but the value they already have. Such as summing the number of widgets sold during the month of April, 2003. Since April 2003 is far gone, that formula can be readily replaced by a fixed value.
To quickly turn a formula into a fixed value:
1) select it
2) copy it
3) paste-special (values)
this works on cells and ranges alike.
- Brian Withun