What is the oldest known origin of the word "halcyon"?
I can trace the word back to the myth of Alcyone and its connection to the kingfisher, but I couldn't find any information about how the word was formed or where exactly did it come from?
"Halcyon" is a Latinization of the Greek 'ἀλκυών (halkuṓn). This word is composed of two roots hals (sea) and kuōn ([hunting] dog). Hals is used to form names like Halia & Haliakmon, and kuōn has several meanings: dog, guardian, divine servant, shark, &c (See the LSJ entry for κύων: bit.ly/2ro83O4)
Alternatively, kuōn could be from another root meaning something like "born of." So a halcyon is either a "guardian of the sea" or "born of the sea" or, more likely, an intended ambiguity that means both names at the same time, which I think is more in line with the story of the mythical figure.