Ref. Paces. I was taught to use "double pace", i.e. as Kate said, the heel you start off on to it hits the ground. This is, (or was), the Army's pace. As an accurate way of measuring paces, for a parade, display,etc. a 'pace stick' was used, (the thing you'd see Seniour NCO's WO's carrying), this measured a 'standard' Army pace as 30"
As for keeping count of pacing distance, the usual practice was to use at least two people counting paces. I use/d 62 paces per 100m in 500m 'bounds', using fingers to count. 2 'bounds' per km. Unless you needed to be really accurate for distances greater than a km we normally 'switched' to using timing, the further you go using pacing the more chance errors can happen. That's why we used more than one person pacing.
If you think the distance is wrong, there's someone to "check" with. If you have different distances you would check the map or use an 'average' of the two. Then find a feature that will show exactally where you are.
I was also 'taught' natural navigation and have found that I still use it, even if I don't realise it at the time!!