> Who collected broadsides printed in the USA in the second half of the 1800s?

Among folklorists, seemingly nobody. But a very large number are available online from the Library of Congress, and many more are available in songster form from Google Books, etc.

No "Flying Cloud" before 1922.

Maybe the song first appeared (as a poem) in some local newspaper. If so, it hasn't been found in a search of vast newspaper databases.

Maybe it appeared as part of a vaudeville act or in a medicine show. (Consider "Sung with great success by Leonard D. Geldert.")

Maybe the author circulated it in handwritten copies, and/or (in preferred fashion) sang it on shipboard or elsewhere many, many times.

It's so good that many hearers (relatively speaking) would have wanted to learn it.

Those are the only theories I can think of at the moment. None address the date of composition. Personally, I'm reluctant (in general) to date things to a date far earlier than their first report (ca1880-1892 in this case) without concrete evidence.

Folk ballads were not considered "newsworthy," except when readers wrote in to ask for a complete text of one song or other. These were usually parlor songs, and the practice seems to have become common only after 1900.