According to Colin McEvedy, in 737 after the Muslim Conquest of Spain, 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 (somewhere between 15 and 22,000).
Over the next several hundred years the northern Christian kingdoms slowly ground away at the Muslim position in Spain. By 1000AD Leon was south of the Douro. At this time, as @mh01 mentioned, Cordoba had passed Toledo, and was in the 23-49K range, making it the largest city west of Constantinople (50-125K). No city in all the territory under Papal authority could even boast 15K. Colin figures the closest was Venice at around 8-9K.
By 1100AD Leon had captured Toledo, and by the latter half of the 13th century, the Christians took Seville and Cordoba as well. This left Muslim Spain only the little Emirate of Granada on the southern Mediterranean coast.
This is where things stood in 1346, 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.