It can do it, there is a library for rotary encoders. You can funge that to just do counting. You are looking for a decoder function for rotary encoders. I assume it's incremental A follows B. http://www.arduino.cc/playground/Main/RotaryEncoders
Well the Arduino mega does allow for five user interrupt pins I believe, so three of them could service the channel A of each of the three encoders. There would need to be 3 input pins assigned for the three channel B signals from the encoder. From there each of the three ISR functions could maintain an up/down counter just as shown in some of the encoder libraries.
So the question is, are three asynchronous 17khz interrupts too fast to prevent missing steps? The ISR needs to be written 'lean and mean', but my gut says I think it can be handled. Keep in mind that the ISR triggers have the option on when the interrupt is generated, change, low, etc. So perhaps some playing with the trigger type can help prevent missing steps for a tradeoff of a small amount of timing skew.