Occurs on later British broadsides that could be as late as 1900, printed by Sanderson of Edinburgh and Forth of Hull. There is a copy in the Baring Gould BL collection that has a different first line 'Years have passed since first he met me.'. Usual broadside start is 'Once I loved with fond affection'. I'd say an American origin is likely, possibly a minstrel song. According to Kilgarriff Tommy Armstrong of Tyneside set his 'Trimdon Grange Explosion' to it in 1882. The tunes I know to 'Go and Leave me' aren't the one I've heard sung to 'Trimdon Grange' but that's likely a more recent setting. Sharp calls it 'The Dear Companion' in the FS from the Appallachians set.