What are some examples of works we read today as poems, but were originally sung, their melodies lost over time?Is a song a poem? What poems were once sung?
There are several possible examples of works we read today as poems, that may originally have been narrated as songs and in many of these cases, melodies could have been lost over time.
One possibility that immediately springs to mind is that of the Norse ballad, or Viking ballad. This form of story-telling through song would have taken place on dark evenings when the light had gone and it would have been one of the few forms of entertainment and education, to an audience perhaps gathered round a fire for warmth. News was also transmitted in the oral form from one country/village to another.
Another name for these is 'sagas' where stories had many chapters over,perhaps, generations. Some stories/songs like these ones have made it through to modern times in different media - such as Beowulf.
Other possibilities include The Tain (Ireland) the old Norse tales.
You are referring to oral epics. These are commonly-known stories, transmitted from folk to folk through song in absentia of a printing press, literacy, or in need to confer information quick. In this case, oral epics were, of course, told from folk to folk in song in order to a) say the same story twice b) remember facts c) nobody could have written it by then.
In Spanish literature you have El Cid Campeador, which is an epic tale just like those in the likes of Beowulf *also once a folk-to-folk sung epic*. The Iliad and the Odyssey were also oral epics sang in song or told like stories.
Some recent examples, however, can be found in African American history and the slave lore, which was nearly entirely based on chant and song.
I am including some links for you to see a diversity of lists available online. Hope it helps!