Taking a closer look at Stefan’s idea here, and considering the concerns people have about the set-window-point/format-mode-line approach, I have implemented a new caching system based on nlinum, with the regular old line-number-at-pos and count-lines underneath; see:

Neither format-mode-line nor window-point manipulation is needed now.  Unlike nlinum, it also does not require an after-change-function, opting instead to save a buffer tick and point-min/max to look for buffer modifications and any narrowing/widening.  In practice it entirely solves the long file scrolling bottleneck, since effectively all line lookups during scrolling hit the cache, and cached computation of all 3 line positions is >50x faster than even format-mode-line was.

Thanks all for your suggestions/criticism/feedback.  What I can conclude is that the default approach line-number-at-pos takes of “counting all newlines from the start of the file” is really painfully inefficient.