Well, I have extracted the problem giving query:
string(913) "SELECT COUNT(*) FROM #__k2_items as i LEFT JOIN #__k2_categories c ON c.id = i.catid RIGHT JOIN #__k2mart AS k2mart ON k2mart.baseID = i.id RIGHT JOIN #__virtuemart_products AS product ON product.virtuemart_product_id = k2mart.referenceID LEFT JOIN #__virtuemart_product_manufacturers AS manufacturersXref ON product.virtuemart_product_id = manufacturersXref.virtuemart_product_id LEFT JOIN #__virtuemart_product_prices AS prices ON product.virtuemart_product_id = prices.virtuemart_product_id WHERE product.product_parent_id = 0 AND i.published = 1 AND i.access IN(1,1) AND i.trash = 0 AND c.published = 1 AND c.access IN(1,1) AND c.trash = 0 AND ( i.publish_up = '0000-00-00 00:00:00' OR i.publish_up <= '2013-01-29 21:29:35' ) AND ( i.publish_down = '0000-00-00 00:00:00' OR i.publish_down >= '2013-01-29 21:29:35' ) AND c.id=2 GROUP BY product.virtuemart_product_id ORDER BY i.ordering ASC"
It is constructed initially by the function getTotal() in 'components/com_k2/models/itemlist.php'. There are additional JOIN statements with k2mart and virtuemart and the query in the basic k2 component function getTotal() isn't constructed with those JOIN statements so I figure that the k2mart plugin is adding these JOIN statements.
//Edit: Disabling K2Mart plugins results in working k2 pagination
This query returns a total count of '1' where it should be something like 15. I can't figure out which part of the query is limiting the total count and more important why it is limiting the total count. It must have something to do with the update..
NOTE: WHERE product.product_parent_id = 0 is a hack since I only want to display parent products. However this worked in the previous version and disabling it doesn't solve the problem.