MmWave FANETs play an increasingly important role in the development of UAVs technology. Fast neighbor discovery is a key bottleneck in mmWave FANETs. In this paper, we propose a two-way neighbor discovery algorithm based on a spatial multi-channel through cross-layer optimization. Firstly, we give two boundary conditions of the physical (PHY) layer and media access control (MAC) layer for successful link establishment of mmWave neighbor discovery and give the optimal pairing of antenna beamwidth in different stages and scenarios using cross-layer optimization. Then, a mmWave neighbor discovery algorithm based on a spatial multi-channel is proposed, which greatly reduces the convergence time by increasing the discovery probability of nodes in the network. Finally, a random reply algorithm is proposed based on dynamic reserved time slots. By adjusting the probability of reply and the number of reserved time slots, the neighbor discovery time can be further reduced when the number of nodes is larger. Simulations show that as the network scale is 100 to 500 nodes, the convergence time is 10 times higher than that of the single channel algorithm.