Air traffic flow management (ATFM) is the key driver of efficient aviation. It aims at balancing traffic demand against airspace capacity by scheduling aircraft, which is critical for air navigation service providers in delivering secure and sustainable air transport. Nowadays, the scale of scheduled aircraft grows dramatically along with the sharp increase in air traffic demand, which brings heavy pressure to efficient scheduling. Regarding safety and efficiency as two fundamental objectives of air transport, this paper proposes a cooperative co-evolutionary algorithm to solve large-scale multi-objective ATFM problems. First, a new multi-objective co-evolution framework with an evolving external archive is devised, in which the subcomponents collaborate with each other via the knee solution of the archive. Second, a novel fuzzy decomposition method is specifically designed to split the large-scale ATFM problem into small-size subcomponents by utilizing the spatiotemporal correlations of aircraft. During optimization, the proposed algorithm can continuously receive feedback from the optimization process and make the decomposition more likely better suited to the problem. Third, a new contribution-based probabilistic resource allocation mechanism is developed to automatically assign the computing resources to the unbalanced subcomponents. Finally, a test suite with different scales extracted from real air traffic data is created. Extensive experimental results show that, given the same number of fitness evaluations, the proposed algorithm significantly outperforms the state-of-the-art baselines in terms of effectiveness on all the benchmark instances.