One basic instrument seems to have been the odometer, described in Vitrivius' book, Chapter 9. Similar mechanisms could also measure miles by sea, by using a paddled wheel.
Thus, as the wheel proceeds, it acts on the first drum-
wheel, the tooth of which, in every revolution, striking the
tooth of the upper wheel, causes it to move on; so that when the
lower wheel as revolved four hundred times, the upper wheel has
revolved only once, and its tooth, which is on the side, will
have acted on only one tooth of the horizontal wheel. Now as in
four hundred revolutions of the lower wheel, the upper wheel will
only have turned round once, the length of the journey will be
five thousand feet, or one thousand paces. Thus, by the dropping
of the balls, and of the noise they make, we know every mile
passed over; and each day one may ascertain, by the number of
balls collected in the bottom, the number of miles in the day's
In navigation, with very little change in the machinery, the same
thing may be done. An axis is fixed across the vessel, whose ends
project beyond the sides, to which are attached wheels four feet
diameter, with paddles to them touching the water.
In modern robotics, wheel encoders are used which also measure axis rotations, and the accuracy of such systems is much dependent on how much the wheel slips. If the wheel has good surface friction in a planar surface, it is possible to get good accuracy. But if the wheel slips (low friction, mud, water, too high acceleration, etc), or if the terrain is irregular so that the wheel jerks and goes up and down, or if the trajectory has many curves, then accuracy is poor.
I expect the accuracy in Roman times would be good in regular paved Roman roads, specially in flat areas and straight lines.
Some of the Roman maps (or other ancient maps) were not maps in the modern sense but what the medievals called Portolans i.e., accurate shapes were not the objective, the point was to get right the sequence of ports, cities, natural features (mountains, harbors, etc), along the coasts and/or roads, and the local distances between them.
Therefore, even if the ship misses her target after crossing the sea, which was common due to navigation innacuracy, after recognizing a city or natural feature, the portolan could tell how far was the desired destination. One such Roman (or medieval, I do not remember) portolan of Italy is in the cover of this famous atlas.
PS1: Do not underestimate the importance of portolans. The point for them was to find the destination, not to decorate a room with beautiful maps. To have a precise map is not so relevant if you do not have precise localization for yourself. Even during the discovery era, the Portuguese had 'roteiros' which were as secret and important as maps. Roteiros (rutters, I think, in english) are just texts describing the sequence of land features and navigational hazards between points A and B.
PS2: I have seen a 1-meter diameter globe from ~1937. It was still noticeably wrong if you looked closely. perfect accuracy, even for the naked eye, came only with satellites.