I was listening to From Our Own Correspondent on BBC Radio 4 this week and there was a report from Krasnoyarsk in Siberia (a town with a big aluminium plant, and thus linked with oligarch Oleg Deripaska, who is in the British news because of controversial meetings he has had with senior politicians). Reporter John Sweeney described the town as the worst dump he'd ever been to (you can listen here until Saturday; click on the Saturday edition button). The 'dump' epithet is ironic, given that the town's name promises something much different.
'Kras' is a common prefix in Russian place names (there's Krasnodar in southern Russia, for instance, as well as several smaller towns - Krasnogorsk, Krasnoarmeysk and others). It comes from the word красный, krasny, which these days means 'red', but which used to mean 'beautiful', hence its appearance in so many place names. Krasnoyarsk's town council website (in English) says the town's name means 'beautiful bank' (Krasnoyarsk is on the Yenisei river).
Red Square dates back to the 15th century, long before 'red' became associated with communism. Its name meant originally the 'beautiful square'; in Russian it's Красная площадь, Krasnaya ploshchad'. Here krasnaya has a feminine adjectival ending to agree with ploshchad', square, which is a feminine noun, but it is from the same root as the 'kras' of Krasnoyarsk.