Herring and Potatoes is a Cape Breton, not Newfoundland song, to the air of Ho Ro Mo Nighean Donn Boidheach. I have the words at home but I won't be back there for a couple of weeks. One verse goes something like this:
When I went up to Boston
They served me fish with frostin'
But heavens it was costing
Too much for a man like me
Give me herring and potatoes
There's nothing tastes as great as
Herring and potatoes
And a good strong cup of tea