My first question is whether you can narrow yoiur categories down even further, so that there is really only less than 12 products per category (and hence, less than 12 products per page and NO pagination required).
I think this is more helpful as a shopper; I simply HATE pagination as a user.
I would personally like a better category tree navigation so I can drill down to the exact category more quickly.
I know it is harder and harder to rank for longtail nowadays, but I still think it is better to have more tightly focused categories wherever possible. (Although i would very much like to hear the opinions of others about this.)