Multi-robot environmental coverage can be widely used in many applications like search and rescue. However, it is challenging to coordinate the robot team for high coverage efficiency. In this paper, we propose a Two-Stage Coordination (TSC) strategy, which consists of a high-level leader module and a low-level action executor. The former provides the robots with the topology and geometry of the environment, which are crucial for robots to learn “where” they should go and avoid invalid coverage. Based on the observed information and the environmental topology, the latter module takes primitive action to reach the sub-goal. To facilitate cooperation among the robots, we aggregate local perception information of neighbors from different hops based on graph neural networks. We compare our method with state-of-the-art multi-robot coverage approaches. Experiments and supporting ablation studies show the superior efficiency, scalability, and generalization of our algorithm especially in unseen style and scale of scenes, and an unseen number of robots.