If we think about things this way, then it becomes likely that Koto = "things, fa ctsfacts" (as in Kotoyue "reasons; accident" or Kotogara "affairs, circumstances") is related to Koto = "speech, word, language" (as in Kotowaza "proverb" or Kotodzukeru "to message, to make excuses"). In the oldest texts, the word for "word" was usually just Koto, and Koto-ba was rare. Context distinguished Koto as in "fact" from Koto as in "word". In time, Koto-ba started getting traction, creating a clearer distinction between them. There's no way to be sure what the -ba originally meant; early Japanese words were written in many different ways, so Koto-ba was written as 言葉、言羽、詞、辞 etc. (while Koto itself could be written as 許登, 去等 and many others). The current consensus seems to be that the early Japanese word Pa/Ba (modern Ha 端) was a general term for "edge, tip, splinter, emanation", including not just leaves but things like Han-pa 半端 "fragment" or Ko-ba 木端 "splinter;wood splinter". So Koto-ba would be the "tip" or "chips" coming off facts and events: language.
You can see this as a kind of folk etymology, a rationalization of the already existing word: Koto-ba are "leaves" because the heart (mind) is the "seed"; the words grow out of it. This passage is from Ki-no-Tsurayuki's Kana Preface to the Kokin Wakashū, which was hugely influential in Japanese thought (comparable to Aristotle's Ars PoeticaPoetics in impact). From then on, you can bet 言葉 would be analyzed as leaves.
What about 万葉集? Do not be misled by the use of the same kanji: this is a Chinese-style word, Man'yōshū, and the Chinese word Yō is not the same as the Japanese word Ha. One may translate the other, but whatever associations we may find for one will not necessarily apply to the other. Sure, it may be the case that Japanese Ha = word = leaf = Chinese Yō; but it might as well be not. Recall that the "leaf" analysis of Kotoba wasn't popular until the Kokinshū; but the Man’yō predates it. There's no "leaf=word" metaphor in the Man'yōshū poems, nor "leaf=poem"; and the word kotobaKotoba in it is written as 事羽 or 辞.
So why is the book called "Anthology of the Ten Thousand Leaves"? The best answer is: Who the hell knows? There's no explanation in the anthology itself, nor in contemporary sources; so there are many respectable Japanese scholars with different theories, without decisive evidence to placate the debate. One theory is that the "leaves of the heartmind" metaphor silently antedates the Kokin, and is used here. Another is that the myriad poems are being compared to the countless leaves of a magnificent tree; another is that the huge, multi-volume collection has many paper "leaves", comparing the book pages to tree leaves (the same metaphor as in English "leaf"). Yet another possibility is that the "leaves" are a metaphor for the "generations" of people:, growing and falling in turn; and this is a collection intended to last ten thousand generations. This metaphor appears in the previous work Kojiki, and currently it's the most commonly accepted theory.