Hi, I'm a historian of 20th century European history, currently writing my MA-thesis on a topic related to the Spanish Civil War. I'm going to try to answer this as coherently as possible, but it's a surprisingly complex matter.

The first thing you've pointed out correctly already in your question is that the 'Moors' feature extensively in Republican propaganda, and that its discriminatory undertone is contrary to the internationalism and progressism of its supposedly leftist foundations. Their presence therein has a longer history than the military uprising that started in 1936.

Before the start of the Civil War, Spain's presence in Morocco between the 1860s and 1920s was hard-fought and often contested by various segments of the populations of the Moroccan littoral, the Atlas mountains, and Western Sahara. Before the catastrophic loss of its Asian and American colonies in 1898, Spain had held towns on Morocco's Mediterranean coast and through treaties and limited military intervention maintained a presence in the region since the 16th century. With the loss of the colonies in 1898, Morocco became the focus of Spain's efforts to regain its imperial prestige. In several disastrous expeditions - the Second (1909) and Third (1911-12) Melilla Campaigns it had failed to make any military gains and secure the mountainous Rif and its rich mineral resources. The horrifying losses of life, equipment by the Army (mostly made up out of poor, illiterate metropolitan conscripts) to no meaningful gain spurred it to raise units in Melilla and Ceuta from the local population. These indigenuous troops were not conscripts, but professional soldiers, which their name - the *Fuerzas Regulares Indigenás * - attests.

In the Rif War from 1920 to 1927 the Regulares developed a reputation for ferocity, reliability, and endurance. Together with the Legión Espanola (the Spanish [Foreign] Legion) the Regulares formed the professional backbone of Spain's overseas armed forces. The fact that these troops consistently saw combat throughout the 1910s and 1920s even though Spain remained neutral in the Great War is of some importance looking ahead to the Civil War in 1936, bear this in mind.

The emergence of the Legión and the Regulares as elite forces was paired with the emergence of a group of officers that supported the expansion of the African empire and had the political network and associates to compete for this in national politics. The Africanista officers included future Nationalists including that of Franco, Millan Astray, Yagüe, an Berenguer. The ambitions of these men were not only in the realm of empire, but also permeated their hunger for promotions. General Primo de Rivera would successfully strongarm the Monarchy into granting him dictatorial powers, and the rest of the officers, including Franco, eventually secured major promotions, including postings at prestiguous military academies.

With the 1931 overthrow of the Monarchy and Primo de Rivera's dictatorship, the Africanistas became one of many factions on the right of the political spectrum, and found allies in the younger Primo de Rivera's Falange Espagnola and other radical or even fascist organisations for the realisation of their ambitions at home and abroad.

The severe economic downturn that hit Spain as part of the Great Depression combined with the incendiary political atmosphere of the early 1930s erupted in wholesale violence already in 1934. In October that year miners in the province of Asturias - the only province of Spain never to see Moorish occupation in Medieval times - revolted and took up arms against the government. Though the government was nominally one of the people, it was a government nonetheless in its decision to crack down on the strikes and the revolt. Fearing that metropolitan units made up out of conscripts would join the miners and threaten Madrid, the government decided to transport Regulares and the Legión under Franco's leadership to Asturias by ship and train to have them suppress the rebellion. There are some pretty good personal accounts of leftist conscripts joining the miners, including the story of Sargento Vazquez, which is central to my MA-thesis - but back to the narrative.

The violence with which Franco put down the 1934 revolt, and the role of Moorish soldiers of the Regulares in it shocked many across the political spectrum, most of all on the left. In particular the trade unions UGT and CNT, and the socialist party PSOE developed an intrinsic hatred of the Regulares.

The military uprising of July 1936 then once again featured the 'foreign' Regulares, again under the leadership of Franco in a central role. During the Defence of Madrid, the CNT, UGT, PSOE, and especially PCE were key players in the organising of militia units to hold off the Nationalists before loyal Republican Army formations could push them back. These political organisations - most of which still had extremely bitter memories to 1934 - organised nearly 20 battalions of militiamen, largely through the famous Fifth Regiment (not the same as the Fifth Brigade; this referred to the International Brigade red.). These militias initially had neither military nor political discipline, but fought extremely tenaciously against Nationalist columns bearing down on the city, including Regulares on the Northern frontage near the city. Throughout late 1936 and early 1937 these troops would continue defending the city, making the Battle for Madrid a centrepiece of the Civil War in general. The fact that the Moors fought the same organisations in 1936 as they did two yeas before is of great significance, and the fact that they did so most ruthlessly and bravely gave them an interesting mixed reputation. On the one hand they were enemy shock troops of commendable bravery (nearly equivalent to the IB troops) as well as an oppressed people, on the other hand they were ruthless in their treatment of prisoners and viewed as defilers of Spain's last Christian vestiges.

By the time the song - Ay Carmela/Viva la Quince Brigada/Viva la Quinta Brigada - became popular, circa autumn 1938 the Republicans had lost significant ground at the Battle of the Ebro. The consequent hardening of the war rhetoric, and the intensification of political propaganda efforts across the board normalised the harsher, discriminatory rhetoric. To little avail, anyway.

Quick grab from my thesis bibliography:

Alpert, Michael. The Republican Army in the Spanish Civil War, 1936-1939 (Cambridge: Cambridge University Press, 2013)

Beevor, Antony. The Battle for Spain (London: Orion Publishing, 2007)

Colodny, Robert G., and Beth Luey (editor, 2009 edition). The Struggle for Madrid – The central epic of the Spanish conflict 1936-37 (New York, NY: Paine-Whitman, 1958/2009)

Engel, Carlos. Historia de las Brigadas Mixtas del Ejército Popular de la República. (Madrid, Almena, 1999)

Kirschenbaum, Lisa A. International Communism and the Spanish Civil War: Solidarity and Suspicion (Cambridge, UK: Cambridge University Press, 2015) pp. 168-187

Menéndez González, Vicente A. “El Sargento Vázquez, el militar olvidado de la Revolución de Asturias de 1934” in Foro Milicia y Democracia Special Edition: ‘80 Aniversario de la Revolución de 1934’ (2014)

This is a fantastic question, and one which has always interested me a great deal, as it points to a profound tension at the heart of both Republican and Nationalist narratives of the civil war. Namely, on one hand we have the Francoist mythology of a national, Christian crusade against Bolshevism, atheism and Freemasonry that deliberately echoed the imagery of the Reconquista – but one which relied on tens of thousands of Muslim soldiers from North Africa, the very ‘Moors’ that the original Spanish crusade had been fought against. On the Republican side, we see a government whose legitimacy was and continues to be based on anti-fascist, progressive and internationalist ideals, drawing at times on explicitly anti-colonial rhetoric, relying in turn on volunteers from dozens of countries (though only a tiny minority of these were not of European background). Yet, we see the Republic utilise crass imagery and rhetoric to demonise the ‘Moors’ fighting for Franco as savage and uncivilised.

These two narratives reflect several decades of history prior to the civil war. Apart from a few smaller coastal enclaves, Spain had occupied most of its Moroccan territory only recently, a move which had not been popular on the left, but played an increasingly important role in the self-identity of the Spanish right, particularly in the army, whose ongoing conflicts against the local population came to shape a generation of officers in the early twentieth century. These so-called Africanistas were central to the coup attempt in July 1936, and the transport of the Army of Africa to the mainland was a crucial factor in shaping the early dynamics of the civil war itself, including their use of Moroccan auxiliaries in mainland Spain. This was not the first time that Moroccan soldiers fought on Spanish soil in the 1930s however – ‘Moorish’ troops had been used to help put down the 1934 leftist uprising in Asturias, where they were accused of brutal conduct against the local population. These same tropes that were used in the leftist press in 1934 – depicting African soldiers as cruel savages who were murdering, raping and pillaging Spanish workers – were to be re-employed during the civil war itself, particularly in the early months, explicitly referring back to both the 1934 uprising, as well as the working-class conscript experience of fighting a brutal and unpopular guerrilla war in Morocco itself.

This initial mobilisation of anti-Moorish propaganda in 1936 focused heavily on sexual fears – the sexual assault of a feminised Spain at the hands of bestial, savage and hyper-sexualised Africans, reflecting an almost textbook Orientalist concern about the sexual power of a racial ‘other’. This is a common enough motif in wartime propaganda, but it had an extra edge here in seeking to condemn Nationalist leaders for letting lose the hated moros on their own people, hiding their own failings as men behind the employment of more virile colonial forces, who fought their battles for them at the front and (allegedly) serviced their wives in the rear. Yet while this rhetoric was designed to mobilise resistance to the coup, it proved counterproductive in the circumstances. As the reputation of the Moroccan soldiers for brutality against civilians and soldiers alike escalated, so too did the panic in the Republican zone. Especially given how poorly trained and disciplined the early Republican militias were, the damage to morale could be disastrous – entire units are reported to have fled once they learned they were facing African soldiers. This in turn bred suspicion and even reprisals over time – Moroccan troops captured by Republican forces often faced summary execution or other forms of ill-treatment, which likely only made them fight all the more ferociously.

In contrast, the Spanish army’s encounters with Africans – not least because of the many defeats they suffered during the 1920s that needed to be rationalised – led to the military elite developing their own imagination of the ‘Moor’, in line with their imperial ambitions. In this vision, Moroccans were noble, martial and courageous, implicitly contrasted with the weakness caused by modernity and its ills in Spain itself. Just as Spanish army officers imagined Morocco as an imperial space in which Spanish virtues of manliness, honour and courage might be rediscovered, so too did the ‘Moor’ become an opponent to be admired and a martial ideal to aspire to. Indeed, the Spanish Foreign Legion – an elite Nationalist unit confusingly composed almost entirely of Spaniards – adopted many of the perceived customs and practices of their former Moroccan enemies, adopting their war rituals and engaging in the mutilation of captured enemies. On occasion, the perceived brutality of the ‘Moor’ was seen as useful – as a weapon of terror against conquered populations and enemy armies, though as the war went on, Nationalist propaganda became more and more likely to downplay the savagery of their allies, and by the end of 1936, Moroccan troops were no longer serving in independent units in any case.

Given the centrality of Christianity to the Nationalist cause, as the war went on it became clear that the use of Muslim troops in Spain could easily be framed as hypocritical, a perception furthered by Republican propaganda. Especially given the association between the Republic and anti-clerical violence, this was an increasingly important line of attack for pro-Republican propaganda, attempting to undermine Francoist claims to Christian sympathies abroad. As the Nationalists had brought Spain’s traditional (and anti-Christian) enemy back to Spanish soil, they had no basis to claim that they represented traditional Spanish values. In contrast, Nationalist propaganda emphasised the religiosity of the Muslim soldiers, and seeking to portray the ‘Reds’ as the new foreign ‘invaders’ of Spain seeking to destroy Spanish Christian civilisation, a struggle in which Moroccan ‘brothers’ were welcome allies against the true Marxist enemy. This discourse of brotherhood, naturally enough, was not one of equality – a reality demonstrated clearly enough by postwar divergences in the services and treatment of Moroccan veterans of the civil war compared to their Spanish counterparts.

Such was the temptation to focus on Nationalist hypocrisy, Republican anti-colonial propaganda was surprisingly muted, to the consternation of some of its supporters, who saw the chance to promote anti-colonial uprisings in Nationalist African territory by promising colonial subjects their independence. Some propaganda, in turn, focused on Nationalist manipulation of their Moroccan allies, who were duped into fighting by false promises of high pay, land and women, that Moroccans, like the Republicans, were simply victims of international fascist exploitation. Yet these representations were both contradicted by the dominant representation of the ‘Moor’ as a racial enemy of the true Spain, whose participation in the civil war exposed the true cynical face of Spanish fascism.

You've already received some great answers directly on your question; I'd like to add a bit on the history of the reconquista rhetoric that both sides in the civil war were drawing on, as /u/crrpit shows. I'm looking at the term reconquista which is intimately tied up with ideas of a medieval Christian Iberia that's opposed to a supposedly "inferior" Muslim other.

Reconquista is a very loaded term for various reasons. First, it's meaning of a Christian "reconquest" of Iberia from the supposed Muslim invaders is clearly highly ideological. It goes back to medieval Castilian sources, who justified their wars by drawing long parallels from their kings to mythical visigothic rulers of Northern Spain, to say that Iberia had "always" been Christian. Of course neglecting the long history of Christians and Jewish people living under Muslim rule in Iberia between the 8th and 15th centuries.

Next up, the term reconquista -not the concept - was popularised only from the 18th century. It became more popular as a founding myth especially in the 19th century tied then to growing Spanish nationalist ideals. This is why by the early 20th century the reconquista rhetoric had taken enough of a hold in popular Spanish imagination that - seemingly quite paradoxically - both republicans and falangists extensively drew on it (including the moro term) to denounce the other side more effectively.

Lastly, this focus on medieval Iberian, Christian Spanishness was also further developed by historians under the Franco regime, making the term reconquista possibly even more politically charged with connections to fascism and/or right nationalism. The term is still being used in current academic literature, but usually these caveats are at least mentioned.

I go into more detail on this in this answer - would really recommend the other answers in that thread too for more especially on the medieval background.

As you already received some great summaries and answers, I'll add just two additional points I deem important to the overall question.

The image of the "brutal moor" was not only fostered by propaganda of both sides and the century old perception of the "moor" as the other, but also based on an exaggerated but nonetheless cruel reality of the war and recent events. While the rebellion of 1934 was obviously the most recent one, I would argue that the so called Desastre de Annual in the summer of 1921 was equally important. In what was basically a chaotic rout and a complete collapse of the frontline, around 10.000 Spanish soldiers died in the surroundings of Melilla, 3000 of them being killed after having surrendered to the enemy. While retaking the lost territory during the following weeks, Spanish troops basically encountered a horror show of cruelly mutilated corpses. Those horrific descriptions made it into every account of the event and filled the pages of newspapers and magazines for weeks and months to come. Later on during the second Republic it became popular among the right, to compare the Spanish left to its colonial population. Spanish workers were thus accused of even worse atrocities than committed by the "moors" in 1921 and the mountains of Asturias became 'Spain's Rif'. What happened in 1934 and during the early stages of the Civil War was in a certain way a colonial war turning inwards: Pillaging, rape, the killing of prisoners and civilians and the mutilation of dead (and sometimes) alive enemies were a common feature of colonial warfare, practiced by both sides in Morocco. What was left out in Spain was the burning of villages and the use of chemical agents.

As already pointed out, the use of Moroccan troops and the Spanish foreign legion (although 80-90% Spanish) played an important role in Republican Propaganda. In the broader picture, they were often shown along with Italian and German soldiers to ridicule the nationalist propaganda of their opponents. It is difficult to say how widely believed this narrative was, but a look at the numbers of 80.000 Moroccans (if correct), 80.000 Italians, 20.000 Germans and 10.000 Portuguese suggest a certain plausibility.