Help needed on a paged query

Hi all,
I would like to set up a page of products (over 8000 in total)
I would like to show it as a paged query of lets say 30 at a time.
However I would also like to put in a filter for main_cat & sub_cat so people can filter them down.

I have kind of got it working, however it only filters the 30 that are shown so not all records show.
Does anyone know the best way to filter it on a paged query ??