What is the most computationally efficient way of generating pseudo-random permutations?
Use format-preserving encryption. The current NIST standards-track mode FFX should be sufficiently fast for your purposes. For your domain size, you might also want to try the swap-or-not shuffle, a new construction that is also pretty fast and dead simple to implement. To get the absolute best speed form these schemes you should use a single AES call as your PRF, preferably with AES-NI instructions if you have them.
EDIT: Any PRP generator based on an oblivious card shuffle should work for your purposes. Here's another reference explaining what that is.