Origin:
I suppose Georgian, since it's the first name of singer Katie Melua, who is originally from Georgia, but now lives in England. I suppose that it's their variant of Katherine and those that apply to that, now she uses Katie as her nickname.
I tried to Google it and came up with this (almost) overall result, which backs up my theory of the origin:
http://en.wikipedia.org/wiki/Ketevan_of_Kakheti
I became very curious about it and I'm wondering if anyone knows more about it and/or if it really has a link to Katherine etc. I hope I supplied enough to get someone started.
Thanks in Advance. :-)