An event could well become legendary right away as rumors spreads by word of mouth through common populace, or whatever circles who hold interest in the events.
I think it is more a question on how long actual facts can coexist with the legend. (Unless the legend is so strong that people will believe it over factual records, in which case the legend will start right away).
But, concerning actual factual records I would say it depends on the records in where the events would be stored:
Types of records
Medieval societies were quite interested in certain records, most notable lineages of royalty and nobility (and religious officials). If the legend concerns the fate of royal or noble lines one would expect them to be written down carefully.
The next level of importance is ledgers on ownership claims, debts, deals, taxes and such economic matters. Such texts will be carefully maintained while they are relevant, and sink towards oblivion when they cease to be relevant.
Lastly there would be notices, town-crier scrolls and such.
In each case, the staying-power of each depends on the interest people have in keeping the information. You can see it as if the information falls out of scope.
Scopes of records
The scope of royal lineages lasts as long as their claims to thrones, relatives and associated lines exist. They go out of scope when the ruling elite is completely displaced by another ruling structure that do not respect the old order.
The scope of economic records last as long as they are relevant. If a city gets razed its records go out of scope. If a personal debt or deal is fulfilled or paid it goes out of scope. If an administration is abandoned its records go out of scope.
Short lived documents go out of scope almost immediately.
After information have gone out of scope, it will survive only in old records, libraries and such maintained by learned. Unless the records are of special importance to the librarians and scholars they will be forgotten and risk to disappear. If they are of scholarly interest then only a major catastrophe will destroy them (burning of library of Alexandria), and probably even that is not enough if they are widely copied.
Think in terms of scopes instead of time.
The relevant factors are:
What types of records might describe this event?
What societal structures have an interest in these kinds of records?
What upheavals, replacements, catastrophes have befallen these institutions since the event? Which of them have gone out of scope?
Are the records of scholarly interest?