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

I'm just basing this on a non-researched guess, but I would venture that it has to do with early trailblazing, when one would mark a path in a forest by carving a notch in a tree, at eye-level, to aid in direction.

'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.