For example, in eighteen forty-nine, a religious leader from Massachusetts wrote the words to “It Came Upon a Midnight Clear.”
Does the phrase mean there was already a song - melody - and he put his own lyrics to the song?
No. In English, the words to a song, are the lyrics of a song:
I know all of the words to We wish you a Merry Christmas off by heart!
Consequently the sentence means that a religious leader from Massachusetts wrote the lyrics of (the song) It came upon a midnight clear. It is not clear from the sentence whether he wrote those lyrics before the song (e.g. he wrote the words as a poem and they were later put to music), or if he wrote the lyrics to create a new song from an old tune, or if he wrote the lyrics for a new tune with the intent of combining them into an entirely novel song.
All that we can know from that sentence is that the song's lyrics were written by him, and that he wrote those words in 1849.