Yeah this sounds right. Draw into a bitmap copy of the overworld map. Looks like they make the trail color lighter or darker based on Z height. If the trail needs to be toggle-able then just put it in a different image and use as an overlay.
Very simple and costs almost nothing to generate or store. 