Based on the notion of execution by beheading, the phrase heads will roll means: people will be dismissed, forced to resign, or otherwise stripped of power, especially in the aftermath of a gross failure or political debacle.
This image was popularised by a literal threat of executions made on Thursday 25th September 1930 by Adolf Hitler (1889-1945), Austrian-born Nazi leader, Chancellor of Germany from 1933 to 1945; the most accurate report that I have found is from The Manchester Guardian (Manchester, Lancashire) of the following day, Friday 26th September:
TREATY TO BE “TORN ASUNDER”
German Heads to “Roll in the Sand”
The sensation this morning in the resumed trial for treason here of three Reichswehr officers was the examination of Herr Hitler, the leader of the “Nazis” (National Socialist party), who gained such remarkable successes in the recent general election. […]
In the course of the proceedings the President [of the Tribunal] read a letter in which Hitler said, “In this fight heads will roll in the sand—either ours or those of our opponents. Therefore let us see that the others will roll.”
To this Hitler replied: “Just as soon as German Fascists by legal means have captured political power in Germany they will tear asunder the Versailles Treaty, if necessary by means looked upon by the world as illegal. National Socialists do not regard the international agreements as law, but as something forced upon us. Germany is gagged by the peace treaties. We do not admit our guilt in the war, especially not the guilt of future generations.
“When we oppose these treaties by every possible means we shall find ourselves in the midst of a revolution. We shall oppose these treaties both diplomatically and by evading them entirely. That may be looked upon by the world as an illegal method, but we will not employ it until the party has been victorious. After two or three more elections the party will be in a majority. If we are victorious then we certainly shall establish a new State tribunal whose duty it will be to deal with the criminals of November, 1918. Then heads will certainly roll in the sand.”
In the same issue, The Manchester Guardian published the following report from its own correspondent in Germany:
Adolph Hitler, the “Nazis” leader, gave evidence in the Leipzig trial to-day. He worked himself up into that histrionically emotional state in which he always addresses the public, and had to be cut short again and again by the judges, who reminded him that he was not in a theatre. […]
According to Hitler, when the party has more than 20,000,000 votes (instead of the 6,000,000 it has now), the “Third Realm” of “Nazis” can be established by a simple majority. Then, in the words of Hitler, “heads will roll.” This he “frankly admits.” All traitors (particularly those who made the revolution of November, 1918—the so-called “November criminals”) will be tried by a revolutionary tribunal and sent to the block or the guillotine. (Hitler is apparently incapable of thinking or talking except in terms of historical romance.)
Hitler’s threat was widely reported by British and North-American newspapers, often under the headline Heads Will Roll; the following, for example, is from The Racine Journal-News (Racine, Wisconsin) of Thursday 25th September 1930:
HITLER ATTACKS VERSAILLES PACT
Fascists Will Scrap It, He Says, When (Not If) They Control Nation.
‘HEADS WILL ROLL,’ IS HIS PREDICTION
Sensational Policy Is Outlined Today Before a Listening World.
This cartoon from International Review, by Richard Q. Yardley (1903-1979), was published in The Sun (Baltimore, Maryland) of Sunday 29th September 1935:
Elections in Memel today
Lithuanians say Nazis terrorize voters with cheerful slogan.
“Hitler is coming and heads will roll”.
The Bulgarian politician Vasil Hristov Radoslavov (1854-1929) had made a similar threat in 1914 when he was Prime Minister of Bulgaria, as reported for example by the Manchester Evening News (Manchester, Lancashire) of Friday 17th July of that year:
A BULGARIAN PLOT.
A telegram from Sofia to the Paris “Matin,” to-day, states that M. Radoslavoff, the Premier, yesterday addressing the leaders of the Opposition, declared that he has been informed by the police that the Opposition were plotting against his life and the lives of his colleagues. He added, “Your heads will roll on the pavement of Sofia.”
The Opposition leaders protested, but said they were prepared to sacrifice their lives for the benefit of the country.—Central News.
But the use of the image as a threat is older; the earliest occurrence that I have found is from the Indiana Herald (Huntington, Indiana) of Wednesday 6th January 1858, which published an article about the Lecompton Constitution, that is, the second constitution drafted for Kansas Territory by pro-slavery supporters:
The New York Express, one of the most independent and conservative of all our leading journals, thus expresses itself with a vim in the matter:
‘[…] We dare entertain the belief that when the Washington-made Constitution is brou’t into the Capitol, it will be treated as it deserves. Let it be treated as the Parliament of England treated the tyrannous rescripts of the Stuarts—disfranchising cities, corporations and towns. Treat it gentlemen of the Senate and House of Representatives!—in such a way, as to demonstrate to mankind that the descendants of Hampden and Sydney, on this side of the Atlantic, have not degenerated; but are as true now, as ever, to the cause of Public Liberty. Your friends in office will be led to the block. Let them go! Their official heads will roll on the ground. Let them roll!’