Yes 2 tables would be the best, 1 for main categories and 1 for sub categories.
You should be able to have them in a singel php-page, both add/Edit/delete/move(edit)
As for Menu Writer, did you get the main category to show? And failed showing the sub categories?
I will try make a small sample and put it up when i get back home later today, se if that helps you out.
Here is the sample!