One thing that a Google Books search for early instances of "shame on X" reveals is how common the word shame is in sixteenth- and early seventeenth-century works. Perhaps the connection of shame with original sin (having eaten the forbidden fruit, Adam sees that he is naked and is ashamed) makes it a particularly powerful term in religious discourse, or perhaps honor and shame provided the push and pull of personal motivation in English society at that time.
Shakespeare uses shame dozens of times in his plays (as Chaucer does in his Canterbury Tales two centuries earlier). But in Shakespeare, unlike in Chaucer, the form "shame on [or upon or against] X" appears several times. It seems that, at some point in the 200 years between Chaucer and Shakespeare, idiomatic use of this declarative form began to take hold, although "shame on X" appears not to have been firmly established as a set phrase even in Shakespeare's time.
Was 'cry shame on X' the original form of 'shame on X'?
The original expression from which we retain the truncated form "shame on X" may have been "cry shame on [or of or upon] X." At any rate there are many sixteenth- and early seventeenth-century instances of this phrase. From Thomas Harding, A Confutation of a Booke, intituled An Apologie of the Church of England (1565):
Now who so euer examineth the place truly, must nedes crye out shame on you Defender, who are thauctour. The wordes, if you had listed to haue alleaged them without falshed, be these.
From John Martial, "A Replie to M. Calfhills Blasphemous Answer Against the Treatise of the Crosse" (1566) in English Recusant Literature, 1558–1640:
For he and they teache, that neither God, neither Christ ca[n] possibly be payncted. And yf it be so, then that which the councell saied in that canon, is worshipped, and adored, is neither God nor Christe, but some thing that may be payncted. Wherfore this impugner with his M. the authour of the image homilie, may streeke this councell out of their bookes, and cry shame of their ignoraunce, for bringing that which proueth manifestly against them.
From Thomas Harding, A Detection of Sundrie Foul Errours (1568) [combined snippets]:
Now M. Harding, compare our wordes, and the Councelles wordes together. We saie none otherwise, but as the Councel saith. The Bishop of Rome himself ought not to be called the Vniuersal Bishop: Herein we do neither adde, nor minish, but reporte the wordes plainely, as we finde them. If you had lookte better on your booke , and would haue tried this mater, as you saie , by your learning, ye might wel haue reserued these vnciuil reproches of falshed to your selfe, and haue spared your crying of shame vpon this defender, Harding.
I neuer cried so ofte shame vpon the Defender, as he deserued, and that he is a shamelesse man, it shal now be here as cleerly tried , as euer it was before. I laie three maine Lies to your charge in this mater. Let the worlde vnderstande, how wel ye are hable to discharge them.
From The Tablette Booke of Ladye Mary Ketyes, Owne Sister to the Misfortunate Ladye Jane Dudlie (1577):
Howe innocente, too, was these Amusements, when comparabel to the odious Waie in wiche the Quene [Mary] occupied her time! Her Thoughtes was full of leetel else but signinge awaie of goode Folkes' Lives; soe did Everiebodye crye oute Shame on her and her Ministers when the excellente Bishoppes Ridley and Latimer was burnt at Oxford [in 1555].
From a letter from William Davison to Sir Francis Walsingham (August 24, 1584), in Letters and Papers Relating to Patrick Master of Gray, Afterwards Seventh Lord Gray (1835):
...where [the Countess of Gowrye] falling on her knees and beseeching his Maiesties compassion, Arane, going betwixt her and the King, led him hastely by her, and she reaching at his cloak to stay his Maiestie, Arane, putting her from him, did not only ouerthrow her, wich was easy to do, in respect of the poore ladies weaknes, but marched ouer her, who, partly with extreme grief, and partly with weakness, sowned [swooned] presently in the open street, and was fayn to be conveyed into one of the next howses, where with much adoe they recouered life of her; which inhumanity even their most affectionat frendis do vtterly condempne and crye shame of.
From Matthew Sutcliffe, A Treatise of Ecclesiasticall Discipline (1591):
Circumstances likewise which is the changeable part of their discipline, as themselues giue out, (for they make it like Diana whom Poets feine to be in heauen a goddes, and in earth mortal, and so giue hir diuers names) notwithstanding are with them vnchangeable. for, that the doctor should teach, and the pastor exhort, is a circumstance. for they will haue the fame executed by those two persons, which is a circumstance; or els they cry out shame and confusion of officers. that the magistrate should meddle in making ecclesiasticall lawes, they will not suffer. they meane not to haue the persons altered.
From Henry Barrow, A Plaine Refutation of Mr. George Giffarde's Reprochful Booke, Intituled, A Short Treatise against the Donatists of England (1591):
And as for proofe of their honestie and vertue, that is not material, that is not required or looked after in this busines, except they be so evill beloved as some come to crye shame of them at that verie tyme. Which if they doe, yet must the matters be too badd and broade, that will be received there.
From The Warn-word of Sir Francis Hastinges Wast-word (1602):
Lo heere the truth of Iho[n] Fox, that Husse, was not so much as accused (much lesse condemned) for holding any one opinion against any article of our Christian fayth. But let the reader see the articles in the councel, and then wil he cry shame of Ihon Fox, and all his crooked cubbes though they haue no shame, especially in that they obiect to vs so often the doctrine of our schoole deuines for allowing the punishing of Tyra[n]ts in some cases with so many limitations, conditions, and restrictions, as by vs are set downe therin.
From Stephen Bradwell, Mary Glovers Late Woefull Case (1603), in Witchcraft and Hysteria in Elizabethan London: Edward Jorden and the Mary Glover Case (1991):
Whether it grewe from his owne Corruption, ot from other mens malicious instructions, let him looke unto it, if he love the peace of his conscience. For as these reasons will not support him, whereupon he adventured to ground himselfe, so all other inducing considerations crie shame on him.
From William Shakespeare, Othello (1603), Emillia (Iago's wife) speaking:
Twill out, twill out: I hold my peace sir, no./Ile be in speaking, liberall as the north;/Let heauen, and men, and deuils, let em all,/All, all cry shame against me, yet Ile speake.
From Nicholas Breton, Cornv-copiae. Pasquil's Night-cap: Or, Antidot for the Head-ache (1612):
Anger the rauen, he will flye about,/As though his meaning wee to seize vpon thee;/The goos will gaggle, and the cocke cry out,/And euery other bird call shame vpon thee:/Annoy the larke, and he will hang the wing,/Trouble the nightingale, she leaues to sing;/Onely the cuckoe, which surmounts them all,/She still chaunts cuckoe, whatsoere befall.
From Robert Persons, A Discussion of the Answere of M. William Barlow, D. of Diuinity, to the Book intituled: The Iudgment of a Catholike Englishman liuing in banishment for his Religion &C. (1612):
And what will M. Barlow say hereunto? Doe these thousand Preachers acknowledge vnity in faith and _religion with the Protestants? Why then doe they except against their doctrine, against their opinions? And if they doe not, what impudency is it in these men to cry shame on vs, for imputing diuersity of opinions in matters of faith and religion vnto them, which by the one side and the other, by Puritan and Protestant, by all [B]ible and Tankerd-bearers so earnestly, plainly, and vniformly is acknowledged?
From John Dod, "The Fifth Sermon," in Seven Godlie and Frvitfull Sermons (1614):
Secondly, as the Scripture giues a sound testimonie, so the Lord himselfe will back it, and make it good. The word denounceth shame vpon all sinners; therefore must God of necessity powre it vpon them; for else hee should not bee true in his threatnings.
From Samuel Hieron, Penance for Sinne, or Davids Penitentiall Psalme Opened (1619):
Returned hee home into himselfe, it was worst of all. What could his owne heart doe lesse, then vrge him with his owne fact, and cry shame vpon him for his grosse presumption, or for his fainting so soone euen at the words of a simple Maide? Should he go to his fellow Disciples?
From Edward Elton, An Exposition of the Epistle of Saint Paul to the Colossians, second edition (1620):
Let us therfore looke that our religion, bee not in things vanishing, transitorie, and passing away with the time; there is no doubt,but most of vs, if not al of vs, can discerne the grossenes of poperie, and cry shame on it, in placing religion in not touching, not tasting, or not handling this or that kind of outward thing; yet we our selues (many of vs) haue no other religio[n]. but euen that which is found in vanishing things, in things, passing away together with the time : ...
And from William Whateley, A Bride-Bush; Or, A Direction for Married Persons (1623):
He shameth more that his sinne is before God: then if it were in all mens eyes, and if all men should cry shame on him, he would not be abashed, as he is with holy blushing, that his shame and sinne lyeth vncouered before God.
Incidentally, the expression "a crying shame" may also be bound up with the wording "cry shame on [or upon] X." The first instance of this expression in a Google Books search is from Clement Ellis, The Gentile Sinner; or, England's Brave Gentleman (1660):
He holds it to be (as indeed it is) a crying shame, whilest the Taylor, and the Cobler are justly reckon'd among the Necessary members of a Commonwealth, that the Gentleman, who takes it as an affront not to be thought much better then such Mechanicks, should not be so much as usefull to the place where he lives: or at most, but as the trimming is to a good suit, or the haire to the head, which may be Cut off and thrown away, and no great hurt done to either.
Is "cry shame on X" the progenitor of "shame on X"? The Oxford English Dictionary, Compact Edition (1971) is not especially enlightening on this point. It identifies "shame on you" as the equivalent of such interjections as "you should be ashamed" and "fie for shame," and it finds instances of shame used in this sense going back to 1300—but all of the citations included beneath this definition involve the wording "for shame." Here is the OED's definition (13b), which is subordinate to its more general definition (13) of for shame:
[13.] b. esp. in adjuration or remonstrance. Hence often as an int[erjection] = 'shame on you!' 'you should be ashamed!' ; also fie for shame!
At definition 16a of shame, the OED reaches "shame on [you]" directly:
16. a. In ejaculatory formulae of imprecation or indignant disapproval, as (a) shame (or † a shame) betide (take, etc.) .. ! (b) shame to or on .. ! (c) (the) more shame for .. ! (d) shame! simply. Also for shame!
But the earliest citation that the OED gives for the "shame to or on" subgroup of this definition is from Shakespeare's King John (1595) (quoted in the Shakespeare section of this answer, below), which is considerably later that the earliest instances of "shame on [or upon] X" that a Google Books search finds (and that I note elsewhere in this answer).
A third useful entry in the OED's coverage of shame involves the expression cry shame and appears as definition 16b:
[16.] b. To cry shame on, upon, †of: to express vigorous reprobation of.
The OED's earliest citation for this definition is from Shakespeare's Much Ado About Nothing (1599) (also cited in the Shakespeare section of my answer, below), which is several decades later than the earliest Google Books matches for "cry shame," detailed above.
Instances of 'shame on [or upon] X' in Shakespeare
Shakespeare's plays appeared during a crucial, unsettled period in the evolution of "shame on X" as an idiomatic interjection of denunciation. Alexander Schmidt, Shakespeare Lexicon and Quotation Dictionary, third edition (1902) cites several instances of "shame on X" or "shame upon X" in Shakespeare's work that appear to be echoing a recognized idiom:
[Shame followed] by on or upon: s. on Angelo, Meas. III, 2, 283. Ado IV, 1, 123. John II, 167. R3 I, 3, 249.
Schmidt's references are to the following particular lines. From Richard II (1592), Hastings and Queen Margaret speaking:
Hastings. False-boding woman, end thy frantick curse;/Lest, to thy harm, thou move our patience.
Queen Margaret. Foul shame upon you! you have all mov'd mine.
From King John (ca. 1595), Queen Elinor speaking to Constance:
Queen Elinor. His mother shames him so, poor boy, he weeps.
Constance. Now shame upon you, whether she does or no!
From Much Ado About Nothing (1599), Leonato speaking to Beatrice:
Leonato. Dost thou looke vp?
Friar Francis. Yea, wherefore should she not?
Leonato. Wherfore! why doth not euery earthly thing,/Cry shame vpon her? could she here deny/The story that is printed in her bloud?
From Measure for Measure (1603), Duke Vincentio speaking:
Shame to him, whose cruel striking/Kills for faults of his own liking!/Twice treble shame on Angelo,/To weed my vice, and let his grow!
Schmidt overlooks this match from Henry VI, Part 3 (1591), Warwick speaking:
Did I forget, that by the House of Yorke/My Father came untimely to his death?/Did I let pass th'abuse done to my Neece?/Did I impale him with the Regall Crowne?/Did I put Henry from his Native Right?/And am I guerdon'd at the last with Shame?/Shame on himselfe! for my Desert is Honor.
In addition to all these instances from the 1623 Folio Shakespeare, we have the example from The First Part of the Contention betwixt the Two Famous Houses of Yorke and Lancaster, with the Death of the Good Duke Humphrey (by 1594, a draft of or a reported text from a performance of Henry VI, Part 2 (1591)) that Tim Romano cites in a comment above:
Somerset. Had Yorke been there with all his far fetcht/Pollicies he might have lost as much as I.
Yorke. Yea, for Yorke would have lost his life, before/That [France] should have revolted from Englands rule.
Somerset. Yea, so thou might'st, and yet have governd worse than I.
Yorke. What worse then nought, then a shame take all.
Somerset. Shame on thy selfe, that wisheth shame.
There is obviously considerable variability in the wording Shakespeare uses to express a seemingly very similar core idea in each of these instances. This suggests to me that in Shakespeare's time the status of "shame on X" was not at all the set phrase it has since become.
Other early instances of 'shame on [or upon] X'
One very early instance of "shame on X" appears in Thomas Wyatt, "The louer excuseth him of wordes wherwith he was vniustly charged," in Tottel's Miscellany: Songes and Sonnettes (1557):
Report may always ring/Of shame on me for aye:/If in my hart did spring/The wordes that you do say.
From Edmund Spenser, The Faerie Queen, Book !V (1596):
Ioy on those warlike women, which so long/Can from all men so rich a kingdome hold!/And shame on you, O Men, which boast your strong/And valiant hearts, in thoughts lesse hard and bold,/Yet quaile in conquest of that land of gold!
From George Wilkins, The Miseries of Inforst Marriage (1607):
Sir John Harcop. O Sir John Villen, to betroth the selfe/To this good creature, harmelesse, harmelesse child;/This kernell, hope, and comfort of my House,/Without inforcement, of thine own accord,/Draw all her soule i'th compasse of an Oath;/Take that Oath from her, make her for none but thee,/And then betray her?
Scarborow. Shame on them were the cause of it.
From Thomas Heywood, The Fayre Mayde of the Exchange (1607):
Fiddle. I hold with you Master, if my yong mistresse would like so well of my musicke, that she would dance after no bodies instrument but mine.
Flower. No Fiddle, that were no good conceit.
Fiddle. A shame on you, I thought you would not heare on that side.
From a 1610 translation by John Healey of St. Augustine, Of the Citie of God:
But these vaine titles make Princes go madde, wjereas in-deede they are nothing but the worlds fire-brands, and man-kindes destructions. Shame on the doltish Lawyers, for iangling so about them.
I have included these instances because they show "shame on [or upon] X" in early use without the leading verb cry. It is important to note that cry was sometimes omitted from "shame on X" even in the sixteenth century—most notably in the Spenser example from 1596, where including cry would seem to have been utterly in keeping with the usage of the time. The earlier example from Wyatt seems possibly relevant but I'm not confident that "shame on me" is being used there in the same way as in later instances of "shame on X."
Conclusions
The particular wording "shame on X" appears as early as 1565, in a screed by Thomas Harding, where Harding says "Now who so euer examineth the place truly, must nedes crye out shame on you Defender, who are thauctour." This is significant because it is also the earliest instance I've been able to find of the phrase "cry [out] shame."
Whether "shame on you" descended from the longer-form phrase "cry [out] shame on [or upon] you" is a matter for speculation, but the OED's treatment of shame is not incompatible with such a derivation. In my research, I was surprised and impressed at how many of the early (1620 and before) Google Books matches for "shame on [or upon] X" were also matches for "cry [out] shame."
