Not sure what youre refering to with constrained storage though. The system I notice this most is a low-end server class/high end workstation hardware...
Even on a RAID10 of 10 rotational disks 4GB/4kb (swapped memory/pagesize) random reads hurt significantly. Especially as in most situations swapin produces loads of synchronous reads.
Calculating it with the worst case load pattern (which is not that unreasonable) and a perfect distribution between devices thats:
Obviously in reality it won't be quite that bad and the situation can improve considerably if many process are swapping in (because then you suddently don't have only one synchronous request going on at the time) or if you start doing readahead on swap...