I think modern folks forget some of the old ways. Treebeard kept to the old ways; he counted steps. Someone like Aragorn, in his guise as Strider, would find it normal to unconciously count steps as he traveled, thus measuring distance. The ancient Romans did it; their count of mille passus (1000 paces) is the source of our modern word "mile". Even Hobbits with their walking songs are likely unconciously counting steps as they sing or hum through the verses. So it would not be surprising to me that many members of the company would know the count of steps they climbed, even if they weren't conciously counting them.
I'm a habitual step counter and having been for years, long before I got my first smart watch that could count steps for me. A comfortable brisk walking pace for me is 1000 paces, or one mile, every 20 minutes. Thus, I do about 3 miles per hour (a league). Singing (or humming, like a hobbit) "The Ants were Marching" my stride is a bit shorter than the roman standard, so it takes a count of about 60 to reach a mile. With all Corey's discussion of hobbit songs and hums, I don't recall him ever considering their utitlity as a device for counting steps and measuring distance. But as I said, modern folks forget the old ways.