That is only 400 counts at most making 20,000 counts overkill. There are many more 12 bit ADC options than 16 bit ADC options.
May be I am wrong but as I was expecting to get 2.5mV+-2mV error on 1000mV scale. and at 10000mV it is 25mV+2mV?
Your original message says +/-10 volts with 1 millivolt resolution which is 20,000 counts. But that is overkill for an accuracy of 0.25% + 2 digits where a measurement could be off by more than 25 millivolts.
0.25% is a reasonable target considering the cost of 0.1% and better resistors and a precision reference but it may require calibration of the ADC. I might use an integrated 4 channel ADC to support 2 inputs and 2 calibration inputs so the calibration can be done automatically to remove ADC gain and offset errors.
Something like a 12 bit LTC1594L/LTC1598L would be suitable for a design which does not require calibration. Self calibration using the extra channels will remove the offset and gain errors of the ADC itself leaving 10 bits of linearity or 0.1%. I would probably prefer self calibration to a higher resolution ADC but maybe TI, Analog Devices, or Maxim has a suitable higher resolution part.
I dont think I can get that from a 12bit resolution. or is my error calculation wrong?
If you are taking multiple samples and averaging, then accuracy is limited by the integral non-linearity (INL) instead of the resolution of the ADC assuming all other sources of error are removed. 0.25% + 2 digits is not demanding of even a good 10 bit sampling ADC and some 8 bit sampling ADCs can meet it. The 16 bit ADC I linked as an example has better INL but not enough to support its 16 bit resolution really making it a 14 bit ADC as far as accuracy is concerned and this is common with 16 bit sampling ADCs.
Things get a little weird for the error analysis of the standard deviation calculation to produce an RMS reading. The quantization error of the ADC shows up as an additional noise source which always increases the magnitude of the RMS result but unless the DNL (differential non-linearity) is high, this problem will be insignificant.