Robert Hendrickson, The Facts on File Dictionary of Word and Phrase Origins (1997) has this:
blackmail Sixteenth-century Scottish farmers paid their rent, or mail, to English absentee landlords in the form of white mail, silver money, or black mail, rent in the form of livestock or produce. The term black mail took on a bad connotation only when greedy landlords forced cashless tenants to pay much more in goods than they would have paid in silver. Later, when freebooters along the border demanded payment for free passage and "protection," the poor farmers called this illegal extortion blackmail, too.
Curiously, the term blackmail doesn't appear in Francis Grose, A Classical Dictionary of the Vulgar Tongue (1796), despite its criminal/underworld overtones. It does, however, show up in John Russell Bartlett, Dictionary of Americanisms (1848):
BLACK-MAIL. Formerly, money paid to men allied with robbers to be protected by them from being robbed. —Cowell. In the United States it means money extorted from persons under the threat of exposure in print, for an alleged offence, or defect.
So in the United States, by 1848, blackmail already had very nearly its present-day meaning.
With regard to the origin of the term mail in the sense of "payment," John Ayto, Arcade Dictionary of Word Origins (1990), says this:
English once had a third word mail, meaning 'payment, tax' [12(th century)]. It was borrowed from Old Norse mál 'speech, agreement.' It now survives only in blackmail [16(th century)].
The other two words spelled mail that Ayto covers have the meanings "chain-armour" and "post" (derived from an old High German word for "bag or pouch").
The original meaning of blackmail is less clear-cut than Hendrickson (above) suggests. Indeed, the Online Etymology Dictionary ignores the "tenant's rent" meaning almost entirely in its historical summary of how the term was first used:
From the practice of freebooting clan chieftains who ran protection rackets against Scottish farmers. Black from the evil of the practice. Expanded c.1826 to any type of extortion money. Cf. silver mail "rent paid in money" (1590s); buttock-mail (Scottish, 1530s) "fine imposed for fornication."
Nevertheless, the "tenant's rent" meaning was clearly an early sense of the term. Here are some related entries from Black's Law Dictionary, Revised Fourth Edition (1968):
BLACKMAIL. In one of its original meanings, this term denoted a tribute paid by English dwellers along the Scottish border to influential chieftains of Scotland, as a condition of securing immunity from raids of marauders and border thieves.
Also, rents payable in cattle, grain, work, and the like. Such rents were called "blackmail," (reditus nigri,) in distinction from white rents, (blanche firmes,) which were rents paid in silver. See Black rents.
The extortion of money by threats or overtures towards criminal prosecution or the destruction of a man's reputation or social standing.
Here is the related entry for black rents:
BLACK RENTS. In old English law. Rents reserved in work, grain, provisions, or baser money than silver, in contradiction to those which were reserved in white money or silver, which were termed "white rents," (reditus albi,) or blanch farms. ... See Blackmail.
And finally, here is the entry for the Latin term:
REDITUS NIGRI. Black rent, black mail; rent payable in provisions, corn, labor, etc.; as distinguished from "money rent," called "reditus albi."
Corroborating the reporting in Black's Law Dictionary is this entry from Giles Jacob, A New Law-Dictionary (1729):
ARGENTUM ALBUM, Silver Money, or Pieces of Bullion that antiently passed for Money. By Domesday Tenure, some Rents in Libris Ursis & Pansatis, in Metal of full Weight and Purity : In the next Age, that Rent which was paid in Money, was called Blanch-fearm; and afterwards White Rent ; and what was paid in Provisions was termed Black Mail.
However, this same source, in its main entry for "Black-Mail," makes clear that blackmail in the (relatively) benign sense of rents paid in something other than money was already a thing of the past:
And Black-Rents are the same with Black-Mail ; being Rents formerly paid in Provisions and Flesh.
Most of this dictionary's entry for "Black-Mail" is devoted to the crime of extortion:
Black-Mail, ... Signifies in the North of England, in the Counties of Cumberland, Northumberland, &c, a certain Rent of Money, either of Money, Corn or other Thing antiently paid to Persons inhabiting upon or near the Borders, being Men of Name and Power, ally'd with certain Robbers within the said Counties ; to be freed and protected from the Devastations of those Robbers.
In its main entry for "Black-Mail," Jacobs cites An act for the more peaceable government of the parts of Cumberland, Northumberland, Westmorland, and the bishoprick of Duresme (1601), a law in Queen Elizabeth's reign outlawing the practice of protection-payment blackmail. I should note, too, that Jacobs's New Law-Dictionary only slightly revises the wording present in the 1708 update of John Cowell, A Law Dictionary: or, the Interpreter, which itself goes back in earlier editions to 1607, though I can't say how far back the relevant content in Jacobs and in the 1708 update of Cowell goes.
Returning to more-modern assessments of the original meaning of blackmail, we have Merriam-Webster, Webster's Word Histories (1989), which starts by seeming to affirm the Online Etymology Dictionary's version of events, but then vaguely acknowledges that the black in blackmail might have come into existence as a contrast to white payment (that is, payment in silver). Still Webster's doesn't show any awareness of the use of blackmail as a standard legal term for written or oral tenancy contracts between tenant farmers and their landlords:
blackmail Life was unfair for seventeenth-century Scottish farmers. Not only did they have to struggle to cultivate their land and produce good crops, but they also had to contend with corrupt chiefs who forced them to pay for protection of their land. If a farmer didn't pay the protection fee, these same extortionists would destroy his crops. It is this corrupt practice, not the post office, that has given us our word blackmail.
The mail of blackmail comes from a Scottish word meaning 'rent'. The black in blackmail probably derives from an age-old association between the color black and evil or "dirty deeds." It could also have something to do with the fact that the tribute paid by the farmers was in the form of cattle rather than in silver coin, known as "white money."
Yet another theory is floated in Ernest Weekly, An Etymological Dictionary of Modern English (1921):
Blackmail, orig[inally] tribute paid by farmers to freebooters (Sc[otland] and North [England] is Sc[ottish] mail (still used of rent).... It was perh[aps] called black because often paid in black cattle, rents paid in silver being called white mail.
One can only speculate how confusing things would have been if Scottish farmers had raised proto-Charolais cattle instead of proto-Angus.
My impression from all of these sources is that many of the more-recent ones were either unaware or not fully aware of the legal meaning of blackmail in old English law—which envisioned a contract that was no more coercive than any other contemporaneous landlord-tenant contract was likely to be. Whether blackmail as "protection money" came earlier than blackmail as "tenant's rent paid in kind" is unclear from these sources. All we can say confidently is that blackmail was being used in the sense of extortion no later than 1601 in English law, and that blackmail in the sense of legitimate rent was already deemed a practice of former times in 1708. Still, it would be rather odd to take a term associated with criminal behavior and use it to describe a lawful contractual relationship, whereas the co-optation of the noncriminal sense of the term by people intending it in a later criminal sense raises no such objections (in my mind, anyway).
It is certainly possible that the two terms arose independently of one another. It is also quite possible that blackmail (legitimate rent) is the source of blackmail (extortion), and somewhat less plausible that blackmail (extortion) begat blackmail (legitimate rent).