Those barbarians have a special ability called "last stand". Basically, for every unit you defeat, the rest get stronger. A good strategy is to damage as many of them as possible, without actually killing any. Then when they're all hurt, start picking them off. Easier said than done, if your using lower age troops, but this will make it possible to win.
Use the method Rikus is talking about it works. I beat them using range units from iron age, get to the the mountains and spine. Try to leave 1 space between you and them so there is no counter attack. Best of luck.
I lured the barbarians down out of the mountains, where they have a strong advantage—onto the plains. I took my army into one of the corners, away from all the rocks, hills, mountains: and they had to come after us with no terrain advantage. I also always had at least one mounted archer that could ride out, inflict damage and, at least in some cases, make it back to the main group. The barbarians were easy to pick off when they weren’t standing on rocks.
I’d send mounted cavalry and archers to inflict damage on the barbarian slingers, then get out, if possible.
Iron Age archers proved to be very successful against the barbarians, as well. I had at least two Iron Age archers in every army I fielded against the barbarians.
I had great success using mercenaries in two of the battles in that Barbarian province: I’d get my mercenaries into forests or bushes, where they have an attack advantage; I’d just keep them there until some of the Barbarians had to leave their rocks to come after them—my mercenaries took them out every time, and none of them died.