You really can't make a convincing connection between a tune called Martyrdom and one called The Martyrs without comparing the actual melodies. The metre is a very common one, and the word martyr is not exactly a rarity in Christian liturgy! Until shown otherwise, we must assume that there is no connection.

I hear no particular similarity between Old Martyrs as linked to above and Martyrdom, beyond the metrical form. Here is Martyrdom, as it appears in The Bristol Tune Book (Novello, 1863):

X:1
T:Martyrdom
C:Hugh Wilson
B:The Bristol Tune Book, Novello, 1863.
N:C.M.
L:1/8
Q:1/4=100
M:6/4
K:A
E4|A8 F4|E8 (A2 B2)|c8 B4|A8 c4|e8 c4|A8 c4|B8 e4|
c8 B4|A8 c4|d8 c4|B8 c4|E4 F4 (A2 B2)|c8 B4|A8|]

Rather more of a melodic resemblance, particularly in the first part.

"Celtic" is quite the wrong word to be using, of course; but most of you already know that. There's no need to rake over all the modern misapprehensions associated with the term for the eight millionth time: this is an old thread, after all.

If the melody eventually proves to be traceable with certainty to Scotland, let's call it Scottish, shall we? I don't see a great need desperately to be seeking a Scottish connection just because so many people want the song to be Scottish (and have been sorely disappointed where it comes to the authorship of the lyric) but it would be nice to see it nailed down at last.