The psalm tune "Martyrs" predates the Covenanters - first printed by Hart in Edinburgh in 1615. There were harmonized versions of it early on (I think Hart's book is 4-part arrangements), though most Covenanters preferred not to use arranged versions.

I have the ABC and a discussion of how it evolved in the modes tutorial on my website. The rhythm changed as well as the mode. My guess is that it was the most-sung tune in the history of Scotland.

Some of the traditions Nairne would have had in mind are described in the Handbook to the Church Hymnary.