There are two aspects to this: physically getting the encoders in there and doing something with the signals.
I'll deal with the computational part first since that applies to any platform. At the top end of the performance, the motors and encoders give you about 10,000 counts per second, and with two motors, that's 20 events per millisecond. So, you would likely need something much more powerful than an ATmega328 type of processor to deal with that and still do something interesting, like maybe some trigonometry.
On the 3pi, the encoders could fit in the original motor postions but they would partially block the expansion port, and getting the motor leads connected to the existing motor connection points would be tricky. You can get around that by going to the extended brackets, which would let the encoders fit without blocking anything but would also make your wheels stick out more.
The encoders fit in the Zumo chassis, though you will have to figure out how to get the wires from there to your own electronics (our existing Arduino shield does not support the encoders, so it's not a useful starting point even if you had something more powerful than a regular Arduino to plug into it).
I am happy to hear you figured out your problem. For anyone else reading this, I should point out that the three batteries in series make it a 36 V system, not a 36 watt system (that will depend on the current).
Just changing the batteries for higher capacity ones shouldn't cause your motor to die. However, there might be other factors like the new batteries being heavier, which could put more strain on your motor and lead to the failure.
You also wrote "batteries" (plural); if you originally had something like two in parallel and changed it to two in series, you would have gone from 12 V to 24 V, and that could definitely lead to your motor wearing out quickly.
A final thought I have is that the motor is not necessarily what broke; have you verified that independently? The things like higher load and higher voltage that could damage your motor could also damage the control electronics.
As long as you are talking about "amps per hour", you do not understand it. "Per" means you are doing division, so something like "watts per hour" is very different from "watt hours", which is watts *times* hours. Units like amps and watts are already rates (coulombs per second and joules per second, respectively).
As for your main question, I specifically went over it in the post, and you got it right in your follow up post, except for the "per hour" part: a 2Ah, 10C battery can deliver 20 amps.
We have what should be a final configuration for the corresponding sensor board, so we just have to do initial production and make the product web pages and documentation. We should have that done by the end of the week.
How well different battery types handle high loads is generally a very relevant consideration, but your ~2 A discharge rate is not that much for these batteries, so the alkalines having 5x the capacity should far outweigh the variations in high-discharge rate characteristics.
This is not that complicated, and your latest question is whether 26 is bigger than 17. If you gave two more similar numbers, like 17 and 19, you should just try it and time it if it matters much if one does 8 hours and the other does 8.5.