How does common mode range include the negative rail?
We know what the conditions are for dual rails (±5V) and single supply (0 to 5V), so if you had one rail at say -2.5V and one at 5V then the common mode hexagon would be streched from the 



Something like this: 


The hexagon or diamond plot is scaled with the Vcc range:

Source: AN-1401


  Although in-amps appear agnostic to the input common-mode voltage,
  internally, they till must address this voltage. Common-mode voltages,
  especially as they approach the supplies, can cause the internal nodes
  to saturate when the external input and output voltages may otherwise
  be within range. The diamond plot represents this imitation by plotting
  the combination of every headroom limit, including the input range,
  the output range, and the internal nodes. The diamond plot is a
  boundary plot that shows he achievable output voltage (VOUT) range for
  any given input common-mode voltage (VCM), or equivalently, the input
  common-mode voltage range for which a given output voltage can be
  produced.


Source: AN-1401


  How do the devices like AD8220 handle the common mode voltage equal to
  the negative rail or even lower voltage (Take a look at figure 30 of
  AD8220 datasheet) ? 


It scales with the diamond plot, the negative rail would be the lowest voltage


  Does the operation of the amplifier degrade if the Vcm be close to the
  end of its range? Or it will work good as long as Vcm be within the
  range no matter where in the range?


The signal will not be a subtraction when the input signals are outside of the common mode range, so operation is affected. If you are in the common mode range of both the inputs then the instrumentation amplifier will operate as expected.