Don't try using gas laws on ice crystals - it wasn't meant for that, and it doesn't work.
Instead, think about making a snowball. As you try to squish down the ice, you know it becomes more sticky, but if you start with truly "dry" snow, you can't get a good snowball. The reason is that it take a lot of energy to melt even a little bit of snow temporarily - long enough to make water which then re-freezes and makes the snow stick together and become ice.
Now think about the snow below a tire. If the snow starts out fluffy, it will be compacted by the car. As it becomes compact, the force of friction between the crystals will cause local heating. Because your car produces a lot of pressure, there is enough friction in the snow to cause some real heating and melting.
Whether this happens or not will depend on the composition of the snow - and on the shape of the tire and the weight of the car. But the fact that you observe it tells me that there is a combination of conditions in which the snow does melt - and the only way to supply the energy needed for this is through the friction / compression of the snow.
Note that the tires themselves also heat up a little bit - but they will heat very little on snow, because the major heating mechanism in a rolling tire is due to the mismatch in area between the tire "in the air" and the tire "touching the ground" (see for example this answer). When the road surface is slippery, that mechanism is less effective; instead, the friction that the tire experiences is precisely due to the fact that the snow is being compressed: in effect, the tire is always "rolling uphill", and it has to do work. Yet the center of mass never goes higher - instead, the snow is being compressed. And that is the source of the work, and the heating of the snow. Which will cause "sintering" under the right conditions (no, I'm not sure that you can use that word with snow, but it seems appropriate to describe the phenomenon). You can estimate the amount of work done against the snow by seeing how much harder it is to drive in soft snow than on a flat surface - the difference is the work done to compress snow.
I don't have good numbers for that - but I do know that when I was driving a 4x4 on a beach (soft sand), it was getting very poor gas mileage: on the order of 5 mpg for a car that would normally get around 20. This means that the engine had to work almost 4x harder than usual, close to its peak power. If we say that it was using 75 hp just to push through the soft stuff, at a velocity of 20 mph, then we get the work done per meter covered as about 6300 J; assuming that it's the front tires doing the compressing, with a width of 25 cm each we compressed an area of 0.5 m$^2$ meaning that there is about 12000 J / m$^2$ or 1.2 J / cm$^2$ available.
The latent heat of fusion of ice is about 330 J/g, so all that power, distributed like that, could melt only a few mg of snow per square cm (or 1 gram per meter for each of the two tire tracks). That doesn't seem enough to explain what you are observing: there just isn't enough power in an average car to melt the snow it drives over.
