Looking into this if find two numbers are often repeated concerning this topic, a low estimate of 56,000 and a high range of 72,000 or more. These numbers appear across the web at various history focused sites, and a few recent books. The question concerning the validity of these claims has even popped up on other question sites like reddit and Quora.
But to start to find anything close to sources for these figures we have to go back over 100 years, to a book on The History of the Criminal Law of England, vol 1 (1883), by James Stephen
In his book Stephen makes some calculations to extrapolate a possible number of executions across England based on the percentage of sentenced individuals which were actually executed in some select locations. Page 468:
If the average number of executions in each county was
only twenty, or a little more than a quarter of the number
of capital sentences in Devonshire in 1598, this would make
800 executions a year in the forty English counties. The
number of executions was notoriously very great.
I believe this little calculation is the basis for the 56,000 number bantered about the Web. But the numbers don't add up yet. If we calculate the 800 execution per year, over the 36 year span of Henry VIII, we only get 28,800 executions. To get to 56,000 we need more.
Another work, from 1904, discussing the use of the death penalty in England, gives us a source for the higher end figure of 72,000 and provides the more we need based on Stephens number. From The Humane Review, Volume 4, Issues 13-16(emphasis mine).
Until well within the last century hundreds of people were sentenced
to death every year in England I do not know that the French during
the later Middle Ages were particularly scrupulous in the matter of
executions yet if we may believe Sir John Fortescue Chancellor of
Henry VII they were a long way behind us for he says that there were
more persons executed for robbery in England during one year of Henry
VII s reign than in France in seven years Hollinshed the Elizabethan
historian alleged that during Henry VIII s reign there were upwards of
72,000 persons hanged as thieves and vagabonds This amazing total
gives an average of something thing like 1,900 executions per annum As
there were no complete statistics at that period it is possible that
this number may have been exaggerated yet without doubt it
approximated very closely to the truth because when we come to a few
years later to the reign of Elizabeth we have unimpeachable
documentary evidence which shows that the number of executions was
very great It has been calculated by no less a man than the late Mr
Justice Stephen that after making all possible deductions for error
the executions could not have been less than 800 a year The
probability is that they were considerably in excess of 800 there is
even the possibility that they were actually double that number And
this it must be remembered was at a time when the population of the
whole country was less by 1.94 millions than that of Greater London at
the present day.
(the footnote says: The population of England is given as 4,800,000 in 1600)
Here we have an estimate that double the 800 per year was a possibility. 1600 per year over the 36 year reign of Henry VII=57,600. This is how I believe the 57000 number was arrived at. It is a doubling of Stephens original figure of 800 per year.
(For those interested in the 72000 figure it is discussed in an article entitled Two Myths in the History of Capital Punishment from the Journal of Criminal Law and Criminology.)