Relinquere means “leave,” but not just in the sense of “remove oneself from a place,” but also to “leave behind.” E.g. in his Bello Gallico, Caesar writes (1, 12, 2):
Caesar certior factus est tres iam partes copiarum Helvetios id flumen traduxisse, quartam vero partem citra flumen Ararim reliquam esse …
Caesar was informed that the Helvetians had already ferried three parts of their people across the river; that, however, the fourth part was left on this side of the Arar river …
This is what the bracketed addition in the dictionary is trying to express. But this is a metaphorical “behind,” the idea being that we turn our backs on the things or people that we “leave behind.” When we say that we leave footprints behind us in the sand, the “behind” is quite literal, and the verb relinquere does not deliver it.
That does not mean you have to render it in Latin, though. After all, where else are you going to leave footprints? Sometimes, especially in poems, words are just there for the sound or the rhythm. If you are going to render it, I feel post nos would be a more natural choice than retro, which usually describes a direction of a motion.
The English text implies that the relinquere happens at the same time as the discedere, so I would say discedentes is the right form, corresponding directly to the English.
Also, I would prefer reddere to facere, but I suppose this is a matter of taste.
Lastly, I agree with the comments that the English may is not hortative, because it depends on remind. So this ends up becoming:
… commonent ut liceat nobis sublimes nostras vitas reddere et, discedentes, vestigia relinquere …
Edit: As cnread said in his comment, commonere ut typically carries the meaning of suggesting or urging an action, which one would translate as to + infinitive in English, e.g.: commonuerunt ut caveremus = “they reminded us to be careful.” This is not what I intended here; rather, this ut introduces an indirect interrogative clause, literally “they remind us how it is granted to us …” – this in order to avoid a double a.c.i.
Looking this up, I just noticed even my short pocket grammar explicitly mentions this case: monere + a.c.i. = remind; monere + final clause = admonish. In light of this, it is perhaps better to say:
… commonent nobis licere sublimes nostras vitas reddere …