Since you would probably prefer to truly just move an existing category to a new group (and not create new ones and reassign entries as outlined below), this SQL is all you would need:
SET group_id = X
WHERE cat_id = Y OR parent_id = Y
X = new category group
Y = parent category that you want to move to new group
OR clause will catch and move the child categories to the new group as well. Remember to make a backup first.
The edit page in the CP does include an option to filter entries by category and then mass-assign a new category. I've used this to do exactly what you've described.
Filter by your old category to get the entries
Select (check) all entries,
then choose "Add Categories" bulk action from the menu on the bottom right
This is practical if you don't have too many entries that need systematic recategorization (say a few hundred). Just set the limit on the edit page search to 150 entries so you mass-apply categories to a larger batch at each pass.
Otherwise, yes, SQL is the way to go. Just create your new category and note its ID. Then run the following query (backup your database first):
SET cat_id = X
WHERE cat_id = Y
X = the new category ID
Y = the old category ID