If you are displaying pictures (even thumbnails) and using tables, then a long page may take quite a while to load, and depending on the browser, until the </table> tag is hit, nothing gets shown (Broadband users don`t notice this, though).

Having built ecommerce sites that do both, I have found that having a category/subcategory selection goes a long way toward making a site more manageable, especially once you get over 1000 products or so. This also means more pages for the SE's to index, and lets you fine tune the keywords for not only the categories, but the subcategories as well.

If you have control over the database structures, this is pretty easy; if you are using a canned package and it doesn't support 2 or more levels of product heriarchy, then you may be toast.

Also, have you considered an alternate page layout? I have not seen the site, but having 2 or 3 columns of products using thumbnails lets you put more on a "page".