Diane, what I did in a similar situation (though not with anything like as many pages), was to create rules in htaccess for the old to the new url structures using mod rewrite and regular expressions. It's pretty much impossible to say what rules you need without knowing the urls.
That works if your new urls are in some way related to the old ones otherwise you need to do singe redirects for the old urls to the new ones. (Again you can do this all in htaccess, but sh404sef allows you to do redirects too, suggest you ask on their support forums if you don't know how.)
Finally, do you really need to redirect all those old pages? If they didn't have any incoming links, then how much value (i.e. link juice) were they really adding to your site? How much traffic were those pages bringing - if little or none, why not just let Google realise figure out that they're gone and (eventually) drop them from the index?
