The arduino-tiny cores support 16MHz with an external crystal. I've read discussions of driving them faster but cannot recall whether arduino code was being used.
The attiny85 can go up to 16MHz without an external xtal. The maximum 20MHz requires an external xtal, though.
Its just a matter of selecting the clocking fuse values appropriately. I run my attiny85 chips routinely at 16MHz, sometimes (more often than not, actually) even at 3.3V (shock horror!
As long as the arduino core files are compiled for the 16MHz clock option, the timing functions will work correctly.