I'm doing serial comms with 100us period (Using a 4MHz clock on my PIC's) - PIC16F876 to eight 12F675's. I'm not following standard serial comms protocol, so I get away with the 100us cycles, but if you need to do more code between cycles, go for a higher clock speed (8-20MHz)
The only problem is the distance between the PIC and the PC, but I assume seeing that you are using PS2, you will not go more that 2m on the cable.