Are there any sources saying that the ערי מקלט were really built? I heard once that it was too hard to built the all the roads to them so they were never actually constructed. I know in Yehoshua cities are designated to be cities of refuge, but were these cities actually built?
I don't know about the roads, but the Mishna (Makkot 11A) tells us that the mother of the Kohen Gadol would give food and clothing to the accidental murderers in the cities of refuge, so they wouldn't pray for the Kohen Gadol to die.
This certainly indicates that the cities of refuge were operational.
I am assuming that by asking whether or not they were built you mean to ask whether or not they were ever in operation? The actual cities themselves were certainly built. They comprise three cities West of the Jordan (Kedesh, Shechem and Kiriath-arba - Joshua 20:7) and three cities East of the Jordan (Bezer, Ramoth-Gilead and Golan - Deuteronomy 4:43 and Joshua 20:8). Later on, these same cities are listed as Levitical cities (Joshua 21 and 1 Chronicles 6), as foreshadowed in Numbers 35:6.
Some scholars have questioned the historicity of these cities as Levitical cities, but I don't think anybody has ever questioned the operation of the cities of refuge. Since the six of them didn't always all fall within the borders of the land of Israel, dates for their construction and operation vary. If you're interested, John Spencer has an article on this in The Anchor Bible Dictionary, under "Refuge, Cities of" (vol. 5, pp657-658), with a bibliography. That's not a "traditional" source, obviously, and how useful it will be for you depends on your general approach.