First, it is not yellow that is evil, it is gold, and not always.
Yellow is in fact more commonly associated with positive things than negative in Tolkien's work. The Sun is the Yellow Face and strikes fear into the evil Gollum, for instance. It is true that every now and then there is an orc with yellow teeth, or a trail of yellow slime, but those instance are outweighed by soft beams of golden light, the yellow hair of the Rohirrim, yellow drinks, yellow leaves, and so forth.
And even gold is not always evil, despite canonically being the element into which Morgoth put the most of his essence, and of which the One Ring is made. Tolkien is far from averse from using it to show royalty and nobility. Remember, Tolkien is writing from a conservative Catholic viewpoint: greed for what is not one's own is evil, but the riches of the rightful and noble ruler are appointed by Eru. For the Haradim, gold probably signifies their greed, since they are villains.
Now, red is certainly evil. The Red Arrow represents ill tidings:
"The Red Arrow!" said Théoden, holding it, as one who receives a
summons long expected and yet dreadful when it comes. His hand
trembled. "The Red Arrow has not been seen in the Mark in all my
years! Has it indeed come to that? And what does the Lord Denethor
reckon that all my strength and all my speed may be?"
The Return of the King
The Southrons have red banners:
The lines of fire became flowing torrents, file upon file of Orcs
bearing flames, and wild Southron men with red banners, shouting with
harsh tongues, surging up, overtaking the retreat.
The Return of the King
And so forth. Evil mentions of red outnumber even neutral mentions about five to one.
And as for black, well, it is not even a contest. It almost always symbolizes something morbid or outright evil, as examples like the Black Gate, the Black Speech, the Black Hands, the Black Riders, and so forth make abundantly clear. Not to mention Gandalf literally calling Sauron "The Black."
Also, it is not just the orcs who are represented by these colors. The example given was of the Haradim.
With respect to the shields and such, although I did not think of it, there is a very immediate referent: the Roman scuta.
The colors are faded, but as we can see here from the reproductions in the second image, the shield was likely painted bright red and yellow.
As to why they are evil....
Symbolic influences
Both Sauron and Morgoth are constantly associated with fire and shadow. The Balrog, for instance.
It came to the edge of the fire and the light faded as if a cloud had
bent over it. Then with a rush it leaped across the fissure. The
flames roared up to greet it, and wreathed about it; and a black smoke
swirled in the air. Its streaming mane kindled, and blazed behind it.
In its right hand was a blade like a stabbing tongue of fire; in its
left it held a whip of many thongs.
The Fellowship of the Ring
There are also many mentions of red flashes, red fire, and so forth. For Tolkien it seems fire—at least, evil fire—is red:
Right across the floor, close to the feet of two huge pillars a great
fissure had opened. Out of it a fierce red light came, and now and
again flames licked at the brink and curled about the bases of the
columns. Wisps of dark smoke wavered in the hot air.
The Fellowship of the Ring
There is good fire, as wielded by Gandalf, which tends to be white.
In any case, Sauron lives next to a literal volcano, in a land shrouded in darkness due to its miasmata. I think the "shadow and flame" association with Sauron is also fairly self-evident. This probably explains the majority of the red and black references in the context of the forces of Sauron. The roots of this are probably largely Biblical: evil is associated with shadows in the Bible itself, and since at least the Inferno if not early, the Devil has been associated with fire: not merely as a form of punishment, as with the lake of fire in the Bible, but as one of his traits.
Racial influences
Not to put too fine a point on it, but the Haradim and the other peoples allied with Sauron are clearly based on non-white, non-Western ethnicities, and negative versions of them at that. Tolkien even admitted that the orcs were based on Asians.
Why does Z put beaks and feathers on Orcs!? (Orcs is not a form of
Auks.) The Orcs are definitely stated to be corruptions of the 'human'
form seen in Elves and Men. They are (or were) squat, broad,
flat-nosed, sallow-skinned, with wide mouths and slant eyes: in fact
degraded and repulsive versions of the (to Europeans) least lovely
Mongol-types.
The Letters of J.R.R. Tolkien
Yeah....
All of the world, save the West, is essentially aligned with Sauron and engaged in Morgoth-worship at the time of The Lord of the Rings, whence Sauron's limitless armies. If they did not worship Morgoth, they simply worshipped Sauron directly.
In the east and south well nigh all Men were under his dominion, and
they grew strong in those days and built many towns and walls of
stone, and they were numerous and fierce in war and aimed with iron.
To them Sauron was both king and god; and they feared him exceedingly,
for he surrounded his abode with fire.
Of the Rings of Power and the Third Age
Tolkien was clearly influenced by racist conceptions of the forces of the uncivilized East (Asia) and South (Africa and Middle East) arrayed against the civilized bulwark of the West. See also his harangue against the "Orientalization" of Alexander. It is partly in that context that we see the first quote: the Haradim mostly represent Arabs, and their dark hair and eyes, and their red battle paint, are portrayed in a negative, frightening manner specifically in the context of their ethnicity.
It is in this context, also, that we see a description of the evil physical characteristics of the inhabitants of Far Harad:
He now was destroyed; but Gothmog the lieutenant of Morgul had flung
them into the fray; Easterlings with axes, and Variags of Khand.
Southrons in scarlet, and out of Far Harad black men like half-trolls
with white eyes and red tongues. Some now hastened up behind the
Rohirrim, others held westward to hold off the forces of Gondor and
prevent their joining with Rohan.
The Return of the King
Yes, a description of Africans as barely more than trolls that hits all the usual stereotypical elements, and of evil Asians with hachets. Pretty stereotypical.
I would argue that we are not merely seeing Tolkien's association of red and black with Sauron influence his depiction of Sauron's minions, but that these sorts of examples illustrate that Tolkien already associated red and black (the latter more obviously) with non-European groups, as this example and the one in the question illustrate, and that this association also influenced his choice of the colors for Sauron.
Side note with respect to Jews.
While the analysis in the other answer has something to it, and I am loathe to disagree with such a careful scholarly analysis as that cited therein, I am unsure that can be the primary explanation.
Tolkien liked Jews, as hinted at in the famous letter where he criticized a Nazi by saying he regretted that he did not have any Jewish ancestors. That does not mean that he was not prejudiced against them in some way, or that he did not buy into some anti-Semitic stereotypes. In fact, the dwarves have a Jewish influence by Tolkien's own admission, and their defining flaw is made their greed and lust for gold. They are also clannish, industrious, learned, and pretty much every other Jewish stereotype one could think of. But they are not the villains. They are rather a heroic race. I doubt Tolkien would have intentionally based his villainous characters on Jews, or employed imagery that he associated with Jews to characterize the forces of evil. Not to mention that what I mentioned previously about yellow actually being far more often associated with positive figures undercuts the argument somewhat.
Now, it is possible that Tolkien drew on generic Middle Eastern stereotypes to characterize the clothing of the Haradim, and that medieval Christians did the same when they depicted Jews (who, after all, came from the Middle East), but I am skeptical that it goes further than that.