Not common at all, to my knowledge. Don't forget, even Gaius Marius never got a cognomen. To get one you had to have had some genuine triumphs in battles in that region, as well as the support of the Senate.

Off hand, I can only think of two people who got such cognomens. One was Ggaius Marius' superior in Numidia. With the Senate so against Marius and with his connections, he was named Caecilius Metellus Numidicus.

The other is a poor guy named Marcus Antonius. He was severely trounced in a naval battle off Crete, and then again in a land battle on Crete. Then a bunch of pirates forced him to sign a treaty with them. Some wit decided to give him the cognomen "Creticus", which could mean a celebration of a victory at Crete, but which also means "man of chalk".