Regardless of snows muktza status on shabbos, is there an issue in shoveling snow from a paved walk?
At worst:
If snow is muktza, you are doing tiltul min hatzad letzurach davr mutar since you need the walk (Indirect movement by using an object besides your hand for a permissible goal is permitted)
Any melting would be a Rabbinic issue (creating liquid or a safeguard against squeazing grape/olive juices) with the added detractors of being unintentional (aino miskavein) and the liquid will be disposed of without use (holech l'Ibbud), seemingly making this issue moot.
The snow shovel would be a keli shemelachto l'heter *(an instrument which is mostly used for a permitted purpose may be moved for any productive purpose)*if there's no problem with the shoveling itself. At any rate, any shovel (even melachto l'Issur) would be usable to do the snow shoveling.
If anyone wants to answer "Uvda d'Chol", please explain this concept in depth, because to this day, I don't understand how this comes into play unless we're talking about mass vs individual production.