If you tried turning session store off and it didn't make any difference, then the answer to "will it make a difference" is very probably "No".
Yeah, 500 elements on a form was kind of "too enthusiastic". Although with that scenario, the most likely serious problems are going to be MySQL related, hitting hard limits within MySQL for things like maximum query length, etc.
There's no real way for us to provide detailed limits on things, as it depends on a lot of factors beyond our control. And also, in many cases we simply don't know. I've never seen a form with more than a dozen or so calc's on it, and never even thought about the performance issues with having 75+.
Quite honestly, I don't think there's anything I can do to speed up moving between pages, as this involves validation. And even if there's no validations on a given page, we're still going to go through the pre-processing phase, to run all the calcs, and prepare the form for validation / submitting for a variety of gory technical reasons. And as per myu previous post, if yu look at the profiling, between "validation start" and "validation end", you'll get some idea of the amount of processing involved. And that's just the few more obvious contenders for time consumption that I've put profile checkpoints in, there's a whole bunch more going on than shows in the profiling.
About the only way you might speed it up would be to do it as a series of "daisy chained" forms, using copies of the main list/form to emulate the "pages" you have now, where you unpublish everything except the elements on the current "page". But that's a fair amount of work to get going, although simple enough to do a basic proof of concept test - just create a couple of copies for the first two pages, and set up a redirect from "page 1 test" to "page 2 test". The redirect URL from 1 to 2 wuld have to append &rowid={rowid} to the oage 2 URL, so you then edit the partially completed form.
-- hugh