a pic of the problem areas when the legs are in motion would be helpfull, but basically I think it is just a matter of paintweighting skins. also since it is a robot and theres no need for smoothBinding like for deforming skin I would bind everything in a rigid way or just group the necessary parts into the bones hierarchy if you haven´t allready done so.