His stride would almost certainly be longer than that. The increase in the size of the step as compared to speed is actually quite phenomenal. I believe (but don't quote me), that the increase is something like for every 6 inches added, add another 10 mph. Quite a lot, if you ask me. A long human pace for me (and I'm not really tall) is about 2 1/2-3 feet. So, I assume an ent could do much better. Plus, they didn't bend their knees.
Which, comes back to the "staircase" scene. As I said, Ents don't bend their knees, so going down a staircase would be extremely difficult. Go try for yourself to find out, just walk down one without bending your knees. It's very difficult.