Does 葉 mean leaf in Japanese? In 言葉 and 萬葉集, is 葉 derived from leaf? Why is it used for words, language and speech? Thanks.
Let's discuss 言葉 first. It's useful here to distinguish speech from writing, and Japanese from Chinese. If we keep in mind that Japanese had its own independent existence before Chinese characters were even introduced, then we start noticing some relationships between words which where obscured by kanji distinctions. For example, 合う、会う、遭う etc. are all originally the same verb; akai, akarui, akiraka, akatsuki etc. are based on the same root, and so on.
If we think about things this way, then it becomes likely that Koto = "things, facts" (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 by sound 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 木端 "wood splinter". So Koto-ba would be the "tip" or "chips" coming off facts and events: language.
So you see, the question is not quite "what do 'leaves' have to do with 'words'", but rather "why is it that, of all possible ways of writing the early Japanese word Koto-ba, they eventually settled upon 言葉"? As it happens, there's a clear answer for this question:
Japanese songs start as seeds in the hearts of people, then flourish into the myriad leaves of things/words [ことの葉].
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 Poetics 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 Kotoba 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 mind" 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.