Is there any mention anywhere of Klingon or Romulan Starbases which resemble those of the Federation? We know that they have outposts and colonies. I could only think of the Cardassians having starbases as evidenced by Terok Nor (DS9).
Short answer: yes.
Terok Nor isn't listed though it would come under a space station rather than Starbase (Starbases being bigger), DS9 featured 2 such stations, Terok Nor and Empok Nor, Empok Nor was raided for parts by Starfleet for Cardassian spare parts for DS9.
Canon information on non-Federation starbases is thin, given the size of the Klingon and Romulan empires they'd almost have to have starbases for ship maintenance, repair and re-supply.
A Klingon space station, 2 of these were in orbit of the unnamed planetoid in DS9.
I think that the Federation would utilize Starbases more then other major powers would because of their differences in governance and expansion. Starbases serve as administrative hubs as well as supply and maintenance facilities. But because individual races retain sovereignty over their own planets placing expansive bases on planet may be legally and politically difficult if not impossible. But the other major powers don't have this limitation as all their planets are subject to their central government's rule. So planet based hubs would be the more expedient alternative. These hubs would probably have orbiting emplacements that specialize in meeting their various needs, cargo depots, maintenance bays, and the like. There is just no need for the expense and complexity of a structure like a starbase.
Also, one of the benefits of a starbase is it's ability to be placed in a uninhabited system, or in no system at all. As Starfleet is primarily an exploration organization they would lay out their administration and resource hubs to serve that need, not the need to maintain control over territory. The self contained nature of a Starbase allows them to be placed where the most efficiency is to be gained, not limited by the availability of habitable or useful planets.