With a swap partition located on a 10000 RPM disk, average time required for swap read and write requests was found to be 168ms and 355ms, respectively.
I find this rather interesting, as it's orders of magnitude above the theoretical time. Presumably this comes from I/O scheduling?
I'm aware that seek time is a serious problem, but I wonder if you could reduce the number of seek operations by reducing the number of disk I/O operations, full stop. Instead of each page corresponding to one 4kB disk block, you could stuff 2-3 in there and only need to seek and write once instead of 3 times.
If you could workout which 2-3 pages to put in there you could also just put them adjacently on the disk (assuming you weren't very low on swap space). You could do this the adjacent memory pages as the process sees it, however processes tend to assume they can jump all around memory without penalty.
For example 4k page read @ 50MB/sec = 0.08ms + seek time 8ms = 8.08ms and with compression maybe 8.04ms.