Hi JMB,
I agree with Andy and think what you've done will work well.
What CMS does the site use?
I've worked on plenty of big Magento e-commerce sites (from 5k to 5mil pages - so not quite your 60 mil!), but Magento handles this kind of thing very well by default, and in much the same way you have described.
Magento always canonicalizes product URLs to the base URL, no matter what product category they are in.
Eg. a product could be available under multiple categories and it will always use the same canonical tag:
yoursite.com/category-1/product-name/
yoursite.com/category-1/sub-cat/product-name/
yoursite.com/category-1/sub-cat-2/product-name/
yoursite.com/category-2/product-name/
All of these variations would be canonicalized to:
yoursite.com/product-name/
This works perfectly and I've never seen any issues with this.
The only difference with yours is that products are canonicalized to a main category - which actually sounds better to me because then the canonical URL is actually linked from the site (not just "linked" through canonical tags).
I think you'll see some great results with what you've done! But it might take a few months to see the results on a site that size!
Cheers,
David