In the Swahili language, "--kali" is a descriptive suffix-adjective meaning "sharp, fierce". As you may already know, Swahili is a widely-spoken African language which has incorporated words from many other sources, such as older African languages and Arabic. Swahili is sort of the Esperanto of the African continent.
I'm on my way to work right now, but I'll check around today for some more African/Arabic names that pertain to "warrior" for you. I'm assuming that you're looking for boys' names, and not girls' names?