Segundo o dicionário Houaiss (Lisboa, 2003), a palavra lenda vem do latim medieval legenda no sentido de ‘história da vida de santo’. Em português aparece primeiro leenda no século XIII, e só depois lemda e lenda já no século XV. Transcrevo o Houaiss, desabreviando algumas abreviaturas:
lenda s. f. (sXIII cf. FichIVPM) 1 mesmo que LEGENDA (‘vida de santo’) 2 narrativa de carácter maravilhoso em que um facto histórico, centralizado em torno de algum herói popular (revolucionário, santo, guerreiro), se amplifica e se transforma sob o efeito da evocação poética ou imaginação popular 3 narrativa ou crendice acerca de seres maravilhosos e encantatórios, de origem humana ou não, existente no imaginário popular, que frequentemente explicam fenómenos da natureza <a lenda da cobra d’água> → cf. mito 4 por extensão tradição popular <uma cultura com raízes na lenda e não na ciência> 5 por extensão mito popular de origem recente <em torno desse hábil politico criou-se uma lenda que ele soube explorar muito bem> […] ʘ ETIM latim medieval legenda ‘vida de santo’; ver leg-; fonte histórica sXIII leenda sXV leemda sXV lemda [...]
Literalmente, o latim legenda significava (ver comentário do Pablo) ‘(coisa) que se há de ler’, e como explica Raphael Bluteau no seu Vocabulario Portuguez e Latino de 1716 (verbete lenda), “[a]s vidas dos Santos foraõ chamadas lendas porque se havião de ler na liçoens das Matinas, & nos refeitorios das Communidades”. Ora, procurei no Corpus do Português e no Google Books, e até ao século XVIII, era precisamente quase sempre à vida de santos que se referia lenda, nas suas várias grafias. Os primeiros exemplos começam logo no século XIII Corpus do Português)
(ênfase minha em todas a citações):
E depois frey Tomas de Cebrano, de mandada de aqueste manistro geerall, çerca de aquellas coussas que perteemçiam aa regra, compilou o primeiro trautado da Leenda de sam Framçisco
(Crónica da Ordem dos Frades Menores, 1209-85.)
por que na leenda do dicto sancto [Vicente] fez meençom que dous corvos guardarom o sseu corpo das outras aves e cãães quando no campo foy lançado
(Dom Duarte, Leal Conselheiro, 1437/8.)
Nalguns poucos exemplos, de que este na Crónica Geral de Espanha do Conde de Barcelos (originalmente composta em 1344) é o primeiro, lenda parece referir-se ao Corão e tradições religiosas muçulmanas:
Senhor, eu sõõ natural desta cidade e meus avoos forõ daqui sempre alfaqueques [Aulete]. E eu, seendo moço pequeno, cativarõme cristããos. E fezme Deus tanta mercee e deume tal engenho que aprendi a aljamya [Aulete] e toda a leenda dos mouros.
E ha também alguns exmplos poucos, começando na Crónica de Dom João I de Fernão Lopes (1443), em lenda refere-se à vida de uma pessoa importante que não um santo:
Rei de Portugual e primeiro do nome e segunda parte de sua lemda
Nos exemplos atá ao princípio do século XIX fica-se com a ideia que o escritor toma a lenda como verdadeira. Só a partir do século XIX é que se encontram escritores que claramente encaram as lendas de que escrevem como nós o fazemos hoje, ou seja como narrativas não verídicas. O primeiro exemplo claro que encontrei deste uso foi numa tradução de 1841 por A. F. Castilho das Metamophoses de Ovídio:
¿ mas, porque razão, este bom de Ovidio, que tanto em amôres se delicía, passou por alto a Metamorphose, a que este Heróe volatil deveo o ser gerado, a Metamorphose de Jupiter em chuva de ouro ? Á fé, que mais guapa, e refulgente fábula, lh’a não poderia deparar toda a lenda dos Deoses
O seguinte é de 1865, as Lendas e Narrativas de Alexandre Herculano:
A lenda precedente é tirada das chronicas de Acenheiro, rol de mentiras e disparates publicado pela nossa Academia
Por curiosidade, até ao início do século XIX também se encontra lenda com o moderno sentido de legenda, ‘inscrição, texto explicativo que acompanha imagem’.