It sounds like some sort of an idiom, but I haven't found it in any dictionary. Maybe, it means 'lose one's pace', doesn't it? The context suggests it.
Don’t lose your step
Now we’re almost there
Go wash your face and comb your hair
(an excerpt from the song My Love for Evermore by the band Hillbilly Moon Explosion)
To "lose one's step" generally means to break the rhythm of one's walking, usually unintentionally. So, as an example, if you're walking along normally and suddenly hit a patch of slippery ground which causes you to have to stop and regain your stability (but not actually fall), you would have lost your step.
As @Smock commented, it is similar to "falter", although "falter" often has implications that your progress has been broken because you are hesitant or reluctant about something, and can also suggest that it is a more significant or enduring situation, whereas "losing one's step" does not really imply any hesitancy, just that something made you break your normal stride for a moment.
Usually, losing one's step is due to losing stable footing in some way, but not always (you could lose your step because something startled you, for example). If you trip over something, or stumble in some way, that could also be described as losing your step (though in many cases, I suspect people would choose to use the more explicit "trip" or "stumble" instead). It is generally not said when something actually makes one fall down, or if you have to stop walking because something is in your way, etc. It also generally implies that the condition is something that can be quickly recovered from (though it doesn't necessarily mean that it was recovered from quickly, just that it normally could have been).
You are correct that "lose one's pace" is very similar. I think the only real distinction between the two is that "losing one's step" implies a quickly recoverable condition (i.e. only one of your steps was out of place, but the next one could be normal again), whereas "losing one's pace" implies that your rhythm has been disrupted in a way that stays disrupted for at least some time (i.e. it's not easy to get your pace back to normal).
In the context of the quoted song lyrics, I think the phrase has pretty much the same meaning as usual, basically "don't stumble / falter / etc".
In that precise case, the meaning would be similar to "lose oneself" (figuratively, of course) or, indeed, to "lose one's pace".
