To elaborate on johanvdw's answer: Files stored on hard drives use a minimum amount of storage, and the amount of storage they use is incremental and based on the formatted block size. The default windows block size is 4096 bytes, meaning that each file uses at least 4096 bytes of storage, and the amount of space used increments based on the block size. Every time you double the size of your tile width and height (i.e. go from 256x256 to 512x512), you reduce the amount of required tiles by a factor of 4 (or very close to 4 in any case). So if you reduce the amount of tiles by 4, you will reduce the amount of potentially wasted bytes by 3 x block size (you could still waste up to 4096 bytes per 512x512 tile). In practice, it is difficult to predict exactly how much space you will save by doubling the size of your block tiles without generating a cache for a well chosen sample of data.
I ran across an old blog post of someone who reduced their blog size from 512x512 to 128x128 to discover they required 10x the amount of storage as they did before, but the main reason in his case is a large amount of sparse data (i.e. empty tiles) combined with a small tile size resulted in a huge amount of wasted space. The resulting empty tiles were approximately 400 bytes, resulting in 3600 bytes of wasted space for each tile. Combined with increasing the number of required tiles by a factor of 16, resulted in such a large discrepancy between the two tile cache sizes. Url: ArcGIS Server Cache and Optimal Hard Disk Block Size