For the planning, operation and control of multi-terminal voltage source converter (VSC) based high-voltage direct current (HVDC) (VSC-MTDC) systems, an accurate power flow formulation is a key starting point. Conventional power flow formulations assume the constant frequencies for all asynchronous AC systems. Therefore, a new feature about the complex coupling relations between AC frequencies, DC voltages and the exchanged power via VSC stations cannot be characterized if VSC-MTDC systems are required to provide cross-regional frequency responses. To address this issue, this paper proposes a comprehensive frequency-dependent power flow formulation. The proposed approach takes the frequencies of asynchronous AC systems as explicit variables, and investigates the novel bus models of the interlinking buses of VSC stations. The proposed approach accommodates different operation modes and frequency droop strategies of VSC stations, and considers the power losses of VSC stations. The effectiveness and generality of the developed approach are validated by a 6-terminal VSC-HVDC test system. The test system presents the characteristics of the coexistence of numerous VSC operation modes, the absence of slack buses in both AC and DC subsystems, and diversified grid configurations such as point-to-point integration of renewable energy sources and one AC system integrated with multiple VSC stations.