It's from the Irish go leor.* There are a lot of Irish borrowings in English as spoken in Ireland, but only a very few have made it into English spoken elsewhere. In Irish go leor means "enough", but it being so much more used than other Irish expressions, is probably from ceart go leor which means "good enough"/"fine"/"okay" (ceart = "correct/proper/right/" go leor = "enough/sufficiently") being one of those expressions that even Irish people who don't speak Irish, will recognise and use (to state assent, or in reply to Conas atá tú? or even to the English "How are you?").
While ceart go leor didn't make it into English outside of Ireland, galore did. Note that its use copies the syntax of Irish, in that it comes after the noun it is applied to, as with the proverbial "whiskey galore" (a phrase fully of Gaelic borrowing, though the Scottish are a more likely source of whisky/whiskey in English), "crack galore" (which often claimed to be an Irish borrowing, though in truth the Irish got crack/craic from the English) and "etymologies galore"!
Such post-positive adjectives are unusual, and all the more unusual as the general way to use the word, rather than as a few cases of historical significance or poetic origin (e.g. we use "Choir invisible", but otherwise invisible is not post-positive).
This reflects its being a relatively recent borrowing, much as par excellence, another adjective normally used post-positively, is a relatively recent borrowing from French. Forcing English into the patterns of Irish, suggests that those to first make use of it in Irish were more familiar with that language, than English; that is to say, it was borrowed by native speakers of Irish, rather than by Hibernophile Englishmen.
In 1910, Patrick Weston Joyce's English as we Speak it in Ireland, talks both of its use in Ireland, and mentions it's borrowing into the English of England:
The second way in which our English is influenced by Irish is in vocabulary. When our Irish forefathers began to adopt English, they brought with them from their native language many single Irish words and used them as best suited to express what they meant among their newly acquired English words; and these words remain to this day in the current English of their descendants, and will I suppose remain for ever. And the process still goes on though slowly for as time passes, Irish words are being adopted even in the English of the best educated people. There is no need to give many examples here, for they will be found all through this book, especially in the Vocabulary. I will instance the single word galore (plentiful) which you will now often see in English newspapers and periodicals. The adoption of Irish words and phrases into English nowadays is in great measure due to the influence of Irishmen resident in England, who write a large proportion indeed I think the largest proportion of the articles in English periodicals of every kind. Other Irish words such as shamrock†, whiskey, bother, blarney, are now to be found in every English Dictionary. Smithereens too (broken bits after a smash) is a grand word, and is gaining ground every day. Not very long ago I found it used in a public speech in London by a Parliamentary candidate an Englishman; and he would hardly have used it unless he believed that it was fairly intelligible to his audience.
He's a bit after the mark, since the word is attested in English since the 17th Century, but there is some distance from "attested" to "well known".
*There's both the possibility that it came from Scottish Gaelic, and the near-certainty that the existence of gu leòir influenced the borrowing. Irish and Scottish Gaelic are very close languages (much as English and Scots, the Anglic language originally spoken in the Lowlands, are very close) to the point where there are some ways in which the Ulster dialect of Irish is closer to Scottish Gaelic than it is to Irish elsewhere. As such, of the few borrowings from those languages into English outside of Ireland and Scotland it's hard to be certain which was the source, if not both, and the mutual intelligibility would make Irish speakers of English quickly recognise a borrowing from Scottish Gaelic, and vice versa.
†Joyce is certainly correct in shamrock coming from Irish, but wrong in suspecting this is due to the influence of Irish writers for English publications. In 1571 Edmund Campion's Historie of Ireland states, "Shamrotes, Water-cresses, Rootes, and other hearbes they feed upon: Oatemale and Butter they cramme together. They drinke Whey, Milke, and Beefe broth, Flesh they devoure without bread, corne such as they have they keepe for their horses." which can't help but remind lovers of English of Johnson's dictionary's definition of oats. From this began the myth that the Irish ate shmarock. (Edmund Spenser notes the same thing 25 years later, but as a description of a famine in war-torn Munster it may be true). Most likely it was a confusion with seamsóg for wood sorrel (eaten around the world), and seamróg for clover. Either way, it was the English that decided to use shamrock in English, rather than English-speaking Irish. The distinction of shamrock only referring to certain types of clover rather than all might be an English innovation too.