The latest news on Neanderthal genetics suggest that they were not too many. The figure mentioned is of 1500-3500 effective female population size (in Europe), so guess some 5000-10000 total. Does this make sense? And for Homo sapiens too?
In truth I really don't know but I've been making some amateurish estimates for the Franco-Cantabrian region, which apparently was the most populated region of Upper Paleolithic Europe. The Old Country had some 240,000 square kilometers (calculated by adding the areas of regions and provinces/departments that were inhabited back then) and, roughly, a hunter-gatherer group would typically use some 10,000 square kilometers (100 km x 100 km) in Canada (Gamble 2001) but apparently only some 1600 square kilometers (40 km x 40 km) in Cantabrian Magdelenian (Marín Arroyo 2009), roughly what would be now a "comarca", valley or district.
The latter figure fits well with Gamble's findings for Neanderthal foraging areas in Aquitaine (83% of materials from a radius of less than 20 km, no materials from further than 100 km) but would be small for the Carpathian area (48% from less than 20km, 81% from less than 80 km). The colder and drier Central Europe would then require the exploitation of areas closer in range to those of Inuits. Still the situation of the Rhin (only one case mentioned) would be more similar to that of the SW than to Moravia.
So for the Franco-Cantabrian region we could get as many 150 bands or clans, at least for Magdalenian times, when the use of the territory was most intense, each one with their territory of c. 1600 square kilometers.
My biggest doubt is how many people would these bands include: would they be simple bands of c. 30 individuals (20 to 80 following Gamble) or would they be larger groups of maybe 100 people including several of these bands, forming some sort of clan (more than 50 according to Gamble)? Maybe some of my readers has the solution but at the moment I do not. I guess that in earlier times (Aurignacian), these bands could be smaller and that by the end of the Paleolithic (Magdalenian) they would be larger instead.
Just in case here are the results using both figures for band: 30 and 100 people (as reasonable medians):
a. 150 x 30 = 4500 people
b. 150 x 100 = 15,000 people
If you think my estimate for the number of clans is a little high, then sand the figures down a bit. A conservative estimate could be 3000-10,000 people for the Franco Cantabrian region maybe.
And for all Europe? Well, the FC region was without doubt the most densely populated back then, so guess that multiplying this figure by 2, 3 or 4, you'd get a decent estimate. Let's estimate that 1 out of 3 UP Europeans lived in the FC region, that would make the total population of Europe something like 9000-30,000 individuals.
I began this post saying that there were some 5000-10,000 Neanderthals in Europe prior to the arrival of AMHs, based on the most recent genetic data. Does this fit with what I have elaborated? Yes. Even too well I fear.
And I say "I fear" because I really expected AMHs, who after all outcompeted the Neanderthals, to be significatively more efficient, so I do fear to have sinned of conservatism when doing these estimates. But well, this is nothing but an exercise without further pretenses: some thoughts to share with my readers.
After writing this, I re-read Bocquet-Appel's paper (already linked in text but only to justify the FC region as the most populated one) and I just realized he also makes his own popualtion estmates (with different and surely more serious methods). His conclusions are not that different from my own:
Aurignacian: 4400 ppl. (1700-28,400)
Gravettian: 4800 ppl. (1800-30,600)
Glacial Maximum: 5900 ppl. (2300-37,700)
Late Glacial: 28,700 ppl. (11,300-72,600)
Figures in parenthesis are considering the 47.5% confidence interval.