I am trying to move the report from one folder to 'My personal Folder'. Unfortunately its not allowing me to do so. I have edit/delete permission on the folder from which I am moving the report. And My personal folder is my personal one, therefore I have edit permission on it. Ideally this should be possible even without giving the permission "Manage Reports in Public Folders?"
You should have the permission "Manage Reports in Public Folders", as you are trying to modify public folder (moving report from there).
You should be able to 'Save As' the report in your personal folder.
Check Whether "Create and Customize Reports" Checkbox is selected in Profile