A search of Early English Books Online yields three instances of battle (or battel) royal earlier than the 1672 instance cited in the Phrases.org discussion and in k1eran's answer—and two of those three instances explicitly involve cockfighting. The instances occur in books published in 1655, 1662, and 1671.
From Thomas Fuller, The church-history of Britain from the birth of Jesus Christ until the year M.DC.XLVIII (1655):
Humphrey Plantagenet, Duke of Glocester, William Delapole, Duke of Suffolk, Richard Nevil, Earl of Warwick. Betwixt the three last there was as it were a battel Royal in this Cockpit, each of them hating and opposing another. In all these contests their ambition was above their covetousness; it being every ones endeavour not so much to raise and advance himself, as ruine and depress his adversary.
From Thomas Fuller, The history of the worthies of England who for parts and learning have been eminent in the several counties : together with an historical narrative of the native commodities and rarities in each county (1662):
I am sadly sensible, that being to treat of the Worthies in several professions; I shall incur many mens displeasure, in not ranking th[e]m according to their own desires; the rather because there always hath been a Battel Royal about Precedency, betwixt, 1. Swordmen and Gow[n]men: 2. Swordmen and Swordmen: 3. Gownmen and Gownmen:
From Edward Howard, The six days adventure, or The new Utopia a comedy as it is acted at his Royal Highness the Duke of York's theatre (1671):
Featlin: The Ladies are in consultation about us.
Frank: Perhaps they will chuse us by lots or else play us together like a battle Royal of Cocks.
Featlin: But I have design'd my match otherwise, if Fortune be not peevish and hinder me.
These instances indicate that the association of battle (or battel) royal with cockfighting goes back at least to 1655, and they suggest that cockfighting may already have been the primary connotation of the phrase at this early period.
The earliest slang dictionary coverage of "battle royal" that I've been able to find is in Francis Grose, A Classical Dictionary of the Vulgar Tongue, second edition (1788):
BATTLE-ROYAL. A battle or bout at cudgels or fisty-cuffs, wherein more than two persons are engaged: perhaps from its resemblance, in that particular, to more serious engagements fought to settle royal disputes.
But John Badcock, Slang: A Dictionary of the Turf, the Ring, the Chase, the Pit, of Bon-Ton, and the Varieties of Life (1823) has this entry for the term:
Battle-royal—(Cockpit), several cocks put in the pit together. Men (Irish mostly) enact the same kind of Pell-mell trick, at times: 'Tis ever a scandalous proceeding; and often attended with loss of life.
I suspect that Francis Grose was either unaware of the cockfighting sense of the term "battle royal" or chose not to report it in his dictionary of slang. The fact that the phrase was used in the middle 1600s in connection with cockfighting and then appeared in a glossary of sporting slang in 1823 in the same sense strongly suggests that "battle royal" may well have been in continuous use in English cockfighting lingo across the entire period.
