I wonder if it makes more sense to just add a tax on tires. Tire wear for most vehicles should be proportional to actual weight [1] and mileage, modulo tire quality. So just slap a tax on each tire quality type and there is no need for a system to record the mileage and weight of every car.

[1] Commercial vehicle weight is strongly determined by the cargo load.