A much better and more practical idea would be a modest surcharge (5 cents/bag or whatever) which you then get back when you turn them in for recycling (which would be required in every store, not just at recycling centers).
Leclerc stores, in France, have been doing exactly that for nearly 20 years now. 0.07€ for a small bag and 0.15€ for a large. They are not super-sturdy but not bad. They also have more expensive ones, including thermal bags, also refundable.