See my "Joe's Mantis Updates" thread, as I not only name mantises, I also name cockroaches, and sometimes even crickets and in one case a fruit fly (D. hydei that escaped and found its way into the roach enclosure, I decided to keep him there)
For very young mantises, I try for names that would fit both male and female, such as Fortune, Angel, Meek, Kit, Emerald, Jasper, Topaz, Jade, etc.
Older mantises where the gender is easier to tell, I give names that would fit male or female (but not both). Examples include Amber and Chloë.
I have some themes going on for mantises. For the budwings, I have an Egyptian theme: Isis and Osiris. For the male roaches, I gave them names in reference to Cthulhu mythos: Yog-Sothoth, Azathoth, Nyarlathotep - the female roaches are named Azazël, Amalthea and Lilith.
Gemstones a long running theme: Emerald, Peridot, Jade, Topaz, Amber and Jasper. Agate is a possible future name for one of my newest mantises.
Fruit is a theme I gave to 4 Eastern Lubber grasshoppers: Nectarine, Apricot, Pear and OJ (Orange Juice), along with one Differential grasshopper: Apple.
Another theme was names based off of Capriform figures in mythology or other goat-like animals: Baphomet, Fawn, Satyr, Ibex and Capri. Fawn, Ibex and Satyr might be used again as the mantises with those names lived for just a few days.
Some future names might be inspired by The Elder Scrolls: Septim, Quill-Weave, M'aiq, Uriel, Umbra to name a few.
And finally I might start naming some after my characters: Apronice, Sorlia, Pelronir, Zesertet, etc.