One potential way to do this would be to weigh the tires at sale and charge a tax based on the weight of the tire. When the tire is ultimately disposed of, a refund is issued based on the weight of the disposed tire.

This would encourage both avoiding tire wear and proper disposal of tires. That assumes obviously that people don't cheat the system by making tires heavier somehow when returning them.