The story I have heard goes back even further, to a time when maps used black lines, or dashed lines, to denote trails. People would use a red marker to retrace their routes, thus creating the red lines to show their progress.
Not to beat a dead horse but.....when you say it goes way back,,,well the Hobbit was published in '37. The book has a distinct reference to red lining. Gandalf tells Bilbo that all his maps have "red lines" designating what trails he has completed.
This was just a thought I had walking with Marley out to Bridal Veil falls.