This is what The Contemplator has to say.

Lily, the unfaithful lover has appeared in English street ballads (broadside ballads) for more than 100 years. The tune is similar to Lakes of Pontchartrain.

Although this version of the ballad is identified with the American West, Rev. S. Baring-Gould collected versions of Lily of the West in Devonshire, Yorkshire and elsewhere. Baring-Gould felt the ballad was of definite Irish origin (though it may not have been sung to a similar air) and traced it back to at least 1839. The lyrics in Sam Henry's Songs of the People are an Irish version which begins; "When first I came to Ireland..."

Another theory of it's origin traces it back to the West of Ireland during the time of Cromwell.

Cheers!
Ian