You track their positions in a separate almanac
An almanac is a book that publishes forecasted information (tides, weather, planting seasons, etc.) using tabular data associated with a calendar. However, unlike the weather, these rolling cities WANT to be accurate so that they can trade their goods. So, the person driving the city has a vested interest in also keeping a copy of the Moving Cities Almanac to make sure that he is staying on schedule and being where merchants expect him to be at any given date.
So yes, you have a map, but your city is not marked out on the map anywhere, rather it is kept track of in this separate book. Each year, the moving city sends the almanac publisher its schedule for the following year to be printed, distributed, and sold to merchants and anyone else who wants to be able to find these cities. When you consider Code Monkey's answer about how far away these cities can be seen from the smoke cloud, it becomes obvious that fairly large map grids would be sufficient. So using the following map and almanac, you could go anywhere in C5 on the morning of Feb.4th and keep an eye on the Northern horizon, and it wont take long to spot the giant smoke stack coming your way.
But to get even more accurate, you can add Points of Interest as places these cities may stop specifically to do trade; so, if you know the city will be parked just outside of Valonoce from the 9th to the 13th, then this can give a very specific point to meet up with the moving city; so, even if the grid sections are 50 miles wide each, knowing it is going to a specific town or trading post means no time wasted looking around for it at all.
Also, just because these cities can move at 10mph does not mean they are always moving in straight lines over ideal terrain. For starters, they need to stop to actually load/unload cargo and conduct maintenance and they need to also be very carful because of their size to go around bad terrain and avoid farmlands etc that they would destroy if they drive through; so, while two PoIs may only be 30mi appart, it might take the better part of a day to get there if it needs to go slower and more indirectly to get through the marshlands or whatever that separate the 2 points; so, while it can move 240 miles in a day, in practice, it might cover much smaller distances making them easier to track down than you might think.
For context, the first printed almanacs started to appear in the mid 15th century and became very popular up until the internet phased them out; so, they are very appropriate for your tech level, and don't require any magic at all to use.
This makes them accessible to your common merchant and farmer which is FAR better for business than only being able to trade with the magical elite. When every farmer in a community can know when the moving city will show up, then they can co-ordinate their planting, harvesting, etc. to line up with the arrival of the moving city which will maximize the available trade goods for when your moving city does shows up.
Minor Frame Challenge
I would rather not have these cities move on a regular route, and instead I would prefer them to move on the spur of the moment.
This is a terrible idea. Even today with the internet and instant communication, this is not how bulk freight is done (IE: we can but we don't). All bulk supply lines happen on a schedule that has to be planned months and sometimes years in advance or they do not work. They need to line up with planting, fertilizing, and harvesting seasons to make sure the city is where it needs to be to meet supply/demand. If you don't arrive at a certain town in time for the harvest, then the food rots in its silos and people who needed to buy that food die of starvation and the people who needed to sell it suffer massive economic hardships from loosing their whole income for that year. If you don't arrive at another town in time for the first cold front, then they won't have the wood they need to warm their homes and people die from hypothermia. Every time a bulk freighter deviates from their route for even a few days, it will result in shortages, missed trade opportunities, and very palatable human suffering.
On demand goods have historically only been handled by small trade vessels for a good reason; so, if you're going to build a big moving city like this, your only real concern will be in bulk goods and that means keeping to a schedule. If you want a moving city to try to capitalize on spur the moment opportunities, then it should have smaller trucks it can send out to do these on-demand trades, and then those trucks can meet back up with the city later by following the almanac.