700 pages is nothing.
It really depends on what you are trying to do, but if you are a programmer, it would be very simple and fast to decide how to split up the files into the final structure, then get a listing of the new locations and generate the .htaccess file from that, because you know the original location.
I would do it by taking an exact copy of the current data and do this in a different location, so as not to cause any disruption. Once it all works, then do a fast swap.
What would make this more complex is if you had to rename the pages, but I would just write a file that contains old,new and use that to generate the needed changes.
interlinking the pages is another job (in their new locations) but if you are a programmer, as noted in the previous line, it is simple.
Something else you must consider is how will the client manage the system afterwards. Be sure not to put them in the situation that they need you in order to add a new page..
At least you are thinking about this before doing it. I just heard from a friend whose client got someone else to restructure his site and they completely destroyed the fantastic #1 and page 1 ranking they spent years creating.