Cache side-channel attacks significantly threaten the security of TEE-enabled secure architectures such as Intel SGX due to the shared cache resources between the attacker and victim processes. Fine-grained partitioned caches are presented to prevent these attacks, but state-of-the-art partitioned cache designs are faced with the issue of performance losses caused by low cache capacity utilization in all-enclave scenarios, such as multi-tenant cloud environments. We propose VeriCache, a fine-grained partitioned cache, which can support exclusive partitions for large-scale enclaves and is verified secure against side-channel attacks by abstracted cache behavior model checking. To fully utilize cache capacity, VeriCache designs a two-level partition strategy based on a tagged cache architecture and employs a flexible moving boundary between enclaves and non-enclaves. It supports flexible scenarios of the partitions from zero enclaves to all enclaves. We implement VeriCache in the Gem5 simulator for performance evaluation. For a single enclave with a 224KB partition, VeriCache incurs a performance overhead of 11.4% and is slightly better than state-of-the-art partitioned cache, Composable Cachelets (12.7%). In all-enclave scenarios, VeriCache can improve the average performance by 2.7% and increase the LLC hit rates by 7.6% compared to Composable Cachelets.