FWIW I think you have a pretty good choice for origin with Cannibal Islands. Now you mention it I think 'Paddy on the Railway' may have been inspired by Cannibal Islands (Queen of Otaheite).

Of course there are many other tunes that fit this basic pattern but most of the ones I know go back several centuries to the 17th (False Bride/Week before Easter)(Which nobody can deny)etc.