no pins for the encoders on motor shield

Hi everybody,

I need help with my setup, I don't know how to attach all the sensors that I want. the problem is this:

I have two arduino unos, connected by i2c, one has the wifi shield on it, the other the polulu dual vnh5019 motor shield: https://www.pololu.com/docs/pdf/0J49/dual_vnh5019_motor_driver_shield.pdf

they are attached to a dagu wild thumper 4wd frame with 2 wheel encoders (I think these are the ones): https://www.pololu.com/product/2275

now I want to connect the encoders but the motor shield uses already one of the two interrupt pins so my solution to that might be this: http://www.amazon.de/gp/product/B00GNTVGN2?psc=1&redirect=true&ref_=oh_aui_detailpage_o06_s00

can somebody tell me if this might work? would that still produce a decent resolution for the encoder data? I assume there is some multiplexing going on on that board...?

also: can this board and the unos be powered directly from a 7,2v lipo battery?

right now I don't see any other way as there will be at least two other sensors that I want to attach and I don't have that many pins left - would it help if I changed to an arduino mega for example?

thanks for any help!