Moving large number of categories URL Rewrite management and SEO

Question

Need some help and understanding on what do to in the following scenario:

My store has a large amount of products (80k with a multilingual brings the total to 160k for 2 store views) and I am looking at the idea of rearranging the main categories by making some more general categories.

Example

Current:

Category 1 / Child / Child

through

Category 5 / Child / Child

I would like to narrow the category list:

New Category A / Category 1 / Child / Child / Category 3 / Child / Child / Category 4 / Child / Child

New Category B / Category 2 / Child / Child / Category 5 / Child / Child

What kind of impact would this have on my catalog rewrites?, will permanent 301 links automatically be created?

Since this is a large database, would there be any benefit to out right clearing all URL rewrites BEFORE making changes to the category structure?

EDIT:

Here is a print screen of the total url rewrites I have, does this make sense?