One valuable resource I've been utilizing is de Camp's "Hyborian Names," which appeared in Conan the Swordsman: lest you think I've gone soft on the Spraguester, I find myself disagreeing as often as agreeing when it comes to derivations that aren't crystal-clear like Khorshemish. A perfect example is in regards to the etymology of Belesa. Here's what de Camp thinks:
Belesa, Beloso Respectively, the Zingaran heroine of TT and a Zingaran man-at-arms in CC. Origin uncertain; remote possibilities are Belesis, a Babylonian priest of -VII mentioned by Ktesias; a Belesa River in Ethiopia; and Berosos (or Berossus, &c.), a Hellenized Babylonian priest and writer of early -III.
It's been remarked upon that de Camp was an extremely intelligent, erudite and well-informed man who has a curious habit of utterly failing to see the simplest of things. As such, while de Camp was struggling to draw comparisons between a fantastical-Spanish noblewoman and Babylonian priests, I think there's a far simpler origin for Belesa.