The maps I create are based off the style used to create the OpenTopoMap Garmin Maps available for download from https://garmin.opentopomap.org/. I actually discovered the issue using one of these downloaded maps.

I also tested using a Garmin map for the same area downloaded from GMapTool site. These autoroute hiking/walking paths with no problem.

Looking through the lines style file, I yet to find rule that sets properties that prevent autorouting. Perhaps the issue is a difference between mkgmap and say cGPSmapper? It certainly does not sound like a tagging or device issue but how the Garmin map was produced.