Your requirement is surprisingly complex. The fact that you got a useful result from a non-standard MySQL extension to GROUP BY is completely random. Results based on this extension are nothing like a talking donkey. It is not surprising that this works poorly; it is surprising that it works in general.
Here is what you need to do.
(1) summarize sales by products and stores. ( http://sqlfiddle.com/#!9/ca12bf9/12/0 )
select product.product_id, product.shop_id, count(*) sale_count from product join payment on product.product_id = payment.product_id group by product.product_id, product.shop_id
(2) find the number of units sold for the best-selling product in each store by summing up (1) ( http://sqlfiddle.com/#!9/ca12bf9/13/0 )
SELECT MAX(sale_count) max_sale_count, shop_id FROM ( select product.product_id, product.shop_id, count(*) sale_count from product join payment on product.product_id = payment.product_id group by product.product_id, product.shop_id ) findmax GROUP BY shop_id
(3) Attach (1) to (2) to get the identity of the product or products that were sold most in each store. ( http://sqlfiddle.com/#!9/ca12bf9/11/0 )
SELECT a.product_id, a.shop_id, b.max_sale_count FROM ( select product.product_id, product.shop_id, count(*) sale_count from product join payment on product.product_id = payment.product_id group by product.product_id, product.shop_id ) a JOIN ( SELECT MAX(sale_count) max_sale_count, shop_id FROM ( select product.product_id, product.shop_id, count(*) sale_count from product join payment on product.product_id = payment.product_id group by product.product_id, product.shop_id ) findmax GROUP BY shop_id ) b ON a.shop_id = b.shop_id AND a.sale_count = b.max_sale_count
The data you provide has a tie. Thus, two different products appear as the best sellers in one of your stores.
This is a query that places a structured query into a structured query language.