[Guinevere]

The answers to some of your questions can be found in Unfinished Tales.

1) How did the Mellyrn come to Middle-earth?

In "A description of Númenor" there is a description of the trees brought by the Elves of Tol Erëssea to Eldalondë in Númenor.

It's fruit was a nut with a silver shale; and some were given as a gift by Tar-Aldarion, the sixth King of Númenor, to King Gil-galad of Lindon. They did not take root in that land; but Gil-galad gave some to his kinswoman, Galadriel, and under her power they grew and flourished in the guarded land of Lothlórien beside the River Anduin, until the high Elves at last left Middle-earth; but they did not reach the height or girth of the groves of Númenor.

So the Mellyrn came to ME already in the second age, long before the Downfall of Númenor.
When I read this, it made me think of Galadriel's song :

I sang of leaves, of leaves of gold, and leaves of gold there grew:
Of wind I sang, a wind there came and in the branches blew.
Beyond the Sun, beyond the Moon, the foam was on the Sea,
And by the strand of Ilmarin there grew a golden Tree.
Beneath the stars of Ever-eve in Eldamar it shone,
In Eldamar beside the walls of Elven Tirion.
There long the golden leaves have grown upon the branching years,
While here beyond the Sundering Seas now fall the Elven-tears.

At my first reading, I didn't know the meaning of these words, but now they make more sense!
It seems plain, that the Mellyrn came originally from Valinor.
But apparently Haldir doesn't know this, since he says to Frodo:

Alas for Lothlórien that I love! It would be a poor life in a land where no mallorn grew. But if there are Mallorn-trees beyond the Great Sea, none have reported it.

2. The connection with singing in the name "Laurelindorenan"

In the "History of Galadriel and Celeborn" (also in UT) Christopher Tolkien writes in Note #5:

In a note to the text it is explained that Lorinand was the Nandorin name of this region (afterwards called Lórien and Lothlórien), and contained the Elvish word meaning "golden light": "valley of gold". The Quenia form would be Laurenandë, , the Sindarin Glornan or Nan Laur. Both here and elsewhere the meaning of the name is explained by reference to the golden mallorn-trees of Lothlórien; but they were brought there by Galadriel, and in another, later, discussion the name Lórinand is said to have been itself a transformation, after the introduction of the mallorns, of a yet older name Lindórinand, "Vale of the Land of the Singers". Since the Elves of this land were in origin Teleri, there is here no doubt present the name by which the Teleri called themselves, Lindar, "the Singers".
From many other discussions of the names of Lothlorien, to some extent at variance among themselves, it emerges that all the later names were probably due to Galadriel herself, combining different elements: laurë "gold", nan(d) "valley", ndor "land", lin- "sing"; and in Laurelindórinan "Valley of the Singing Gold" (which Treebeard told the Hobbits was the earlier name) deliberately echoing the name of the Golden Tree that grew in Valinor, "for which, as is plain, Galadriel's longing increased year by year to, at last, an overwhelming regret".