Interesting. So far the only thing I've used Maya (PLE) for is a UT2004 game model, and I had the opposite situation. I needed to turn a walk move into a treadmill version.

I started by making a regular walk sequence with a full step for each foot, allowing the character to actually travel the distance. This made it easy for me to see that the steps taken were the same distance, the feet really were anchored, and that the character's weighting would look good enough.

I had two foot controls and a root bone for the skeleton. The controls weren't parented to the root, so the feet stayed in place when I moved the root (and threrefore the rest of the model). I put the root and both controls into a group and then created a character set for that group. (The character set is optional depending on what you're doing. I needed it to create a clip that I could export to the game.) Then I animated that "platform" character set backwards the same distance as the character walked forward. Instant treadmill!

So you might try putting all your root elements into a group and then moving the group along the desired path.