According to Colin McEvedy, in 737 AD, after the Muslim conquest of Visigothic Hispania, the population on the Peninsula was around 4 million. Nearly all of that would have been in Muslim-held territory, as there simply wasn't much else but a couple of little strips of land in the mountainous northern coastal region. Toledo was the only city of any real size in Western Europe at the time (population of 15-22 thousand).
Over the next several hundred years, the northern Christian kingdoms slowly ground away at the Muslim position in Hispania. By 1000 AD Leon was south of the Douro. At this time, as @mh01 mentioned, Cordoba had passed Toledo, and was in the 23-49 thousand range, making it the largest city west of Constantinople (50-125 thousand). No city in all the territory under Papal authority could even boast 15 thousand. Colin figures the closest was Venice at around 8-9 thousand.
By 1100 AD, Leon had captured Toledo, and by the latter half of the 13th century, the Christians took Seville and Cordoba as well. This left Muslim Hispania only the little Emirate of Granada on the southern Mediterranean coast.
This is where things stood in 1346 AD, which is the next time Mr. McEvedy deigns to give me population numbers again. At this point there were roughly 9 million people living on the Iberian peninsula, with perhaps around 2 million of those in Muslim territory.