Well, i think the more accurate solution would be to split your terrain into tiles (browse to the forums, there are solutions for tiled terrains already) and make your characters walk the ammount of tiles you want (making tiles into units of movement, sort of).
You can also have a 3d line, and make your character walk from the begining to the end of it.
Another cool solution is timed movement, you make your character walk in some constant period of time at variable speeds or vice-versa.
And also (as always, there is the hard way to do it), you can project some (arrow) mesh into your terrain and make the characters walk the projected lenght of the arrow mesh....
I would pick the timed movement idea, its accurate enought and stylish
![Cool 8)](./images/smilies/icon_cool.gif)