There are two major reasons. First, in ancient and medieval geographical texts, it was described as being red. The most influential author in this case seems to be Pliny, who notes in his Natural History that:

The sea then makes a two-fold indentations in the land upon these coasts, under the name of Rubrum or "Red," given to it by our countrymen; while the Greeks have called it Erythrum, from king Erythras, or, according to some writers, from its red colour, which they think is produced by the reflection of the sun's rays; others again are of opinion that it arises from the sand and the complexion of the soil, others from some peculiarity in the nature of the water. (6.28)

This is straightforwardly adopted by significant medieval encyclopedias, like Isidore's Etymologies:

The Red Sea is so named because it is colored with reddish waves; however, it does not possess this quality by its nature, but its currents are tainted and stained by the neighboring shores because all the land surrounding that sea is red and close to the color of blood. From there a very intense vermilion may be separated out, as well as other pigments with which the coloring of paintings is varied. Therefore, since the soil has this nature, it is washed away in rivers, and whatever pigment is eroded lends color to the water. It is for this reason that red gemstones are found on these shores, for when a pebble coveredwith this type of soil is eroded in the sand, it has the color of both the earth and the sea. (13.17.2-3)

and Bede's On the nature of things:

42. The Red Sea

The Red Sea takes its name from the rosy colour, which nevertheless it does not naturally have. But it is tinged by its neighboring shores, which are ruddy, with the colour of blood. And therefore red lead and other pigments used in paintings are gathered from there, and red gems. Moreover, the Red Sea is divided into two gulfs. Of these the Persian trends to the north, while the Arabian, which is 115 miles distant from the Egyptian Sea, trends to the west.

But there is also a more straightforward reason, it makes it obvious and easy to find. The Red Sea is a significant landmark on medieval maps, thanks to its prominent inclusion in the Exodus narrative (indeed the path of the Israelites through the Red Sea is included on many mappaemundi, for example, see the Hereford map or the Munich 'Isidore' map). It is entirely natural that they would be interested in highlighting it as a major landmark. And indeed, we have at least one text that explicitly describes this process of colouring a map so as to highlight its various and important features simply to aid the viewer in reading the map.

In the second quarter of the twelfth century one of the most important Parisian master, Hugh of Saint Victor, was giving geography lectures with the use of a large map and we have a text of his description of this map (indeed, the Munich 'Isidore' map is likely a copy of, or at least closely related to, this map at St Victor). (The text itself is actually very likely a set of notes that students had taken down on his lectures, which he likely edited a copy of.) At the beginning of this text, he describes the design and function of a map, explaining that its different topographical features, such as the Red Sea, are coloured differently so that the viewer can easily distinguish between them.

Wise men, both lay people and those learned in ecclesiastical writings paint the world on wood or on parchment, so that they can show images of things to those who wish to know things that are unknown, because they cannot present the things themselves. For not everyone can sail on the ocean, so that they can see the locations of islands, nor can everyone visit distant regions, so that they can perceive their situations, qualities, and divisions. It is for this reason that such a delineation, which is called a mappamundi, is coloured in diverse colors because of the diversity of things, so that the Mediterranean is painted one color, the Red Sea another, rivers another, and mountains another, in order that they can be easily distinguished one from another. And for each thing that is painted in such a mappamundi, a label is written beside it, for images of unknown things without writing or the guidance of words are difficult or impossible to understand. (Trans van Duzer and Dines, Apocalyptic Cartography, 52.)