I have never read The Lord of the Rings so it might be explained in there but it always seemed odd to me that he called himself the Witch King. Can anyone explain the origin of this title?
Nowhere in LotR is it said that he calls himself the Witch-king; the only statement regarding the origin of the name is the following from the Appendices:
The lord of that land was known as the Witch-king
This can be seen as slightly ambiguous: who knew him as the Witch-king? But it's nonetheless clear that this was a name that was given to him by others.
Knowing this it still seems reasonable to ask why he was called this, and I believe that we can begin with two valid interpretations: one is a king of witches, the other is a king who is a witch. I can't find anything in Tolkien to suggest which one (if any) of these is intended, so perhaps it would be better to look at the definition (and particularly the origin) of the word "witch" for some more insight.
Here I'm using http://www.merriam-webster.com/dictionary/witch but any dictionary should be sufficient.
Middle English wicche, from Old English wicca, masculine, wizard & wicce, feminine, witch; akin to Middle High German wicken to bewitch, Old English wigle divination, and perhaps to Old High German wīh holy
It seems quite clear here that "witch", in origin, is derived from both the masculine and feminine OE words, and is related to a gender-neutral word in German/etc, but has only become primarily feminine recently. Tolkien, of course, would have been well aware of all of this.
Going further (and taking a cue from the other origins above), we can see that there are only two usages of the word "witch" in the Silmarillion; one in reference to Morwen:
...they whispered among themselves, saying that she was perilous, and a witch skilled in magic...
And the other in reference to Morgoth:
Hurin Thalion, Morgoth hath bewitched thee...
The latter one is, I believe, extremely relevant here and offers a third interpretation of the name "Witch-king", i.e. "king of witchery", and this interpretation seems most likely to have been Tolkien's actual intention.