Category pages can be moved with the full revision history, by using the Special:Export and Special:Import functions. This requires downloading the xml Special:Export), editing its title tag, and then uploading it (Special:Export).
Would it be possible to do this with a bot?
(I don't know python, but do have some limited competence with pywikipedia bot.)
Thanks!