Well, consider: in the early game you're most likely running level 1 advisers: so about 1 ducat per monarch point. Killing 5,000 natives = 50 monarch points = 50 ducats. If it's costing OP 5 ducats per month to sustain their army on the colony, then if the colony takes more than 10 months (which it will by a long shot, early game), you make an effective profit by killing all the natives. To put it another way, it'd be less efficient to drop a +1 mil advisor to pay for the army, than it would be to have the advisor and have the army massacre the natives.
If a small number of troops can guard the area effectively on the maintainence you would have had your army on anyway, that's usually better (but remember that reinforcements cost money, so it's rarely as good as you think). But genocide still has genuine, though admittedly very situational, application. Doubly so in situations when it isn't practicable to cover all your colonies with armies. (Or if you have an excess of mil points due to having a good mil ruler, which is likely to happen occasionally if you're prioritising trade and colonisation idea groups over military ones.)