Robert_Charlton - 11:12 pm on Mar 30, 2012 (gmt 0)
Pagination and SEO - Maile Ohye
GoogleWebmasterHelp - YouTube - Mar 8, 2012
Google's Maile Ohye examines the issues webmasters face with paginated content: paginated articles, product category listings, etc. She then explains the options available to those webmasters concerned about SEO, including rel="next" and rel="prev" HTML markup.
PS: To echo wingslevel, whatever else you do, definitely sort products by priority. To add a further PS, I've always felt that if a category was much too large, then some further split in categories might be appropriate.