Currency Notes in circulation.
As of March 2016, Rs. 1000 notes in value = 6326 Billion = 6326 Million pieces
As of March 2016, Rs. 1000 notes in value = 7854 Billion = 15708 Million pieces
Assuming all the notes were returned, total notes to be counted, 22034 Million pieces.
A good note counting machine like below can count 1800 notes per minute and can count 24x7 for multiple years. It costs $ 450.
Let's do some math, with the machine above, it would require (22034*10^6)/(1800*60*24) Days for one machine to count all the notes. That is equal to 8501 days for a single machine to count. Given that this was a mammoth operation, and even a simple bank branch seems to have a couple of these machines, RBI could have easily arranged 100 machines and could have counted all the notes in 85 days.
Also given the fact that all the notes are printed by RBI and there would be data available on its weight and volume, they could have just weighed the notes and given an approximate figure. Nobody really cares about the last few hundred crores.