I have to agree with EnzoC on this one.
FROMAIB, VMCA and VMCG are both Indicated Airspeeds(IAS). When you talk about air being thinner, you are describing an increase in Density Altitude, which occurs when either temperature is increased or ambient air pressure is reduced (or both!!). This will indeed mean less control effectiveness at a particular True Airspeed.
IAS, however, is a measure of Dynamic Pressure, and naturally corrects for changes in DA. Therefore at a given IAS, the same amount of rudder authority is available.
If the asymmetric thrust is constant (say, a flat rated turbo-prop or turbo-normalized piston) VMCA and G should remain the same (The only variable here might be nose-wheel steering for VMCG, and it is a certification consideration as to whether it is or isn't counted).
If the thrust from the critical engine reduces, so does the necessary rudder authority, and thus VMCs will be less. This would be the case for most Jets and normally aspirated pistons at higher DAs.
CG also plays a part, as a rearward CG reduces rudder authority.