But you kind of have to compare it with other game activities. What else you you going to compare it with?
500k seem too low imho, an Anaconda NPC gives you what, 350k? A Cyclops is still way more dangerous than that I think.
This might be the problem then... I don't see a Cyclops as "way more dangerous" than an Anaconda NPC, especially with the current level of AX/Guardian weaponry at our disposal.
If you're talking equivalents, I'd go something like:
Cyclops == Elite-rank Assassination Mission
Basilisk == Wing Assassination Mission
Medusa & Hydra: No real equivalent.
Thing is, the NPC targets in those first two only pay out about 200-300k... it's the mission payout which brings that up to 1-3m. Which goes back to my original suggestion, that the key here is fixing the mission payouts/availability, and what counts for the kill, rather than buffing their base payout.