Considering the insufficient control resource for power system frequency stability caused by the large-scale integration of renewable energies, a multi-objective optimal sizing scheme based on an improved Benders decomposition is proposed for the energy storage system (ESS). First, an extended frequency response model is built to analyze the coupling relation between power system active power response and frequency nadir under major disturbances. And the critical transient frequency regulation capability (TFRC) to ensure frequency stability is estimated according to the most severe contingency. Then, a multi-objective optimization model incorporating the TFRC constraint is established for the ESS to minimize the life cycle cost and maximize the operation profits. Additionally, the Benders decomposition method incorporates the genetic algorithm (GA) is used to decompose the optimization model into the master problem and subproblem, which are solved iteratively and alternately. And the global search capability of GA is utilized to enhance the efficiency of searching for feasible solutions in the master problem. Finally, case study results demonstrate that the proposed scheme can improve the operational economy and reduce the number of activated under-frequency load shedding steps, validating its effectiveness.