What is the origin of the phrase "Leave your Mark"?

Here is another guess.

To make one's mark (or leave it) was the way that illiterate people would provide a signature.

If you make your mark then you show up, you indicate your presence. Instead of being a no-one, you have registered your existence in some document. If you appear in court or join an illustrious company then you must sign in or make your mark.

If you look at the history of the phrase 'make * mark' in print, its meaning of signing a document shows up way back and there is a time where it seems to gain new meaning.

I'm not going to make a research project of this. Instead I invite you to read some of the entries thrown up by a search of Google Books for 'made his mark'. I think it is possible to detect how the meaning might have changed.

Even today, we say that someone 'has arrived' to mean that they have achieved success. Similarly it's not too difficult to imagine a meeting or a census where someone says 'Has John made his mark yet?' where they mean 'Has John signed in yet?' or of course 'Has John arrived yet?'.

Not everyone is or was an archer but I would say that a time came in history when nearly everyone in the population had to be accounted for in this way. In olden times, this was the moment that you stopped being a nobody and became, in the eyes of the law, a somebody.

'Chasly from UK' has made the point that to 'make your mark' or 'leave your mark' was essentially to sign your name. In an age when a great many people could not write their own names they used marks, and not just an 'X' as we'd see in movies or read about, but often quite elaborate drawings. From the Oxford English Dictionary:

e. A character made with a pen, usually a cross, used by illiterate persons in place of a signature.
c 1020 Rule St. Benet (Logeman) lviii. 98 Oððe soðes ᵹif he na can stafas, oðer fram him ᵹebeden write & se nicumena mearce do. 1434 in E.E. Wills (1882) 102 And y pray yowe loki thys marke and thys Seell, acorde as y Roger wyl answere afore god. 1588 in Arber Marprel. Controv. 82 William × Stanghtons marke. 1593 Shakes. 2 Hen. VI, iv. ii. 110. 1627 in Barnfield's Poems (Arb.) Introd. 17 Peter Serieantes his × mark. 1766 Blackstone Comm. II. xx. 305 Which custom our illiterate vulgar do..keep up; by signing a cross for their mark when unable to write their names. 1851 H. Melville Whale xviii. 100 Dost thou sign thy name or make thy mark?

So to 'make' or 'leave' your 'mark' was to put your signature on something, and in this sense of creating some kind of impression or legacy it follows from the idea that the person has signed some significant document indicating ownership of property, or some registration or membership form indicating status.

There are so many documents that we sign these days, and so many unimportant ones that it may be hard to imagine why a signature or 'mark' could be an indicator of status. Historically though signatures or 'marks' were more likely to be called for on relatively fewer but much more significant documents than we are used to today. For example documents showing property ownership, or status in the Royal Court, or in the Church, or in workers or professional Guilds and Associations. Signing or placing your 'mark' on these documents was part of gaining property or status.

This association would be enough to explain how the term 'make (or leave) your mark' came down to us. But the Oxford English Dictionary gives a clue to another connection with the expression:

i. Heraldry. A small charge added to a coat of arms as a sign of distinction; esp. in mark of cadency.
1625 B. Johnson Staple of News iv. iv, Were he a learned Herald, I would tell him He can giue Armes, and markes. 1702 [see cadency]. 1718 Prior Henry & Emma 49 This lord..Had brought back his paternal coat enlarg'd With a new mark. 1797 Encycl. Brit. (ed. 3) VIII. 445 Of all the forementioned marks of distinction, none but the label is affixed on the coats of arms belonging to any of the royal family.

In terms of social status in medieval Europe, heraldry was central to how you identified yourself in terms of rank, and how you made your rank known to others. Small indications, or 'marks' allowed you to indicate fine increments in your status. In it's most primitive form this might be equated with 'notches' on a sword or gun indicating 'kills', or the badges or paintings of bombs dropped or missions made by aircraft in war, as in:

Status among bomber crews was clearly displayed (and intended to be understood by others) by the number of combat missions 'marked' on the nose of the plane. The crew - collectively in this instance - were 'making their mark', just as military medals and badges are marks of rank or performance, and just as the marks on heraldic shields, crests and flags signified status in Medieval Europe.

I'd suggest that the usage of the term 'make (or leave) your mark' arose in both contexts (heraldry and signatures-substitutes), each reinforcing each other until the expression became commonplace.