Thanks to everyone who pitched in with suggestions, I have tried to collect all the info in the same answer.
The smallest microcontrollers from each family:
- Atmel ATtiny20-UUR: 1.55 x 1.40 x 0.53 mm, WLCSP-12, 10 gpio,
0.4mm pitch (the winner)
- (new) Cypress CY8C4014FNI-421: 1.56 x 1.45 x 0.4 mm, WLCSP-16, 12 gpio, 0.35mm pitch
- (new) Freescale Kinetis KL03 MKL03Z32CAF4RTR: 2.00 x 1.61 x 0.56 mm, BGA-20, 18 gpio, 0.4mm pitch
- Freescale Kinetis KL02 MKL02Z32CAF4R: 2.00 x 1.95 X 0.56 mm, BGA-20, 18 gpio, 0.4mm pitch
- NXP LPC1102UK: 2.32 x 2.17 x 0.60 mm, WLCSP-16, 11 gpio, 0.5mm
- ST STM32F042T6Y6: 2.70 x 2.60 x 0.55 mm, WLCSP-36, 36 pins, 0.40mm pitch
- TI MSP430G2252: 2.65 x 2.55 x 0.28 mm, bare die, 22 pads
- TI MSP430G2x01: 4.00 x 4.00 x 0.90 mm, QFN-16, 16 pins, 0.65mm pitch
- Microchip PIC12LF1552T: 3.00 x 2.00 x 0.50 mm, QFN-8, 5 gpio, 0.5mm
Sometimes there are other options in the same family which use the same package, but I haven't found anything with a smaller package. This doesn't take into account how much supporting circuitry each chip needs, of course.