I have an Irish 8-page song book print of this dated 1816 and another very similar of 1819, also printed in Belfast - this move the terminus ante quem referred to above, back by 8 years and to an Irish Location:
The Banks of Claudy [inside - A new song called] the B of C], to which are added The answer to the Red Mantle and Paddy Whack, [Cut (faint) – 2 pilgrim like figures, church on hill in left background]
Belfast: Printed in the year 1816
Ulster Museum X 177-1980
Three other Irish song book prints are extant but they are almost certainly later

The earliest plausibly dated ballad sheet print from Ireland is from Cork and cannot be dated more closely than between 1834 and 1846.

However, the Census of Ireland Index of Townlands of 1861 shows eleven places in Ireland spelled Clady and two spelled Claudy, they refer to the Town and Townland on the Banks of the River Faughan not many miles from Derry which Philippa mentioned. Being inclined towards local partisanship, I live to the north of Derry, I'm absolutely, stone-cold definitely sure this is the one.

The ballad trades of Britain and Ireland were closely linked, many songs being exchanged, I'm not surprised the song was widespread in Britain, the people there were not that different from those in Ireland - or vice versa!