In this paper, we propose a new preconditioner for the multi-linear systems with $\mathcal{M}$-tensors by utilizing some elements in the first row and column of the majorization matrix associated with the system tensor. The new preconditioner generalizes the one proposed in (Calcolo, 57(2020) 15). Then, we establish three new preconditioned Gauss-Seidel type methods for solving the multi-linear systems with $\mathcal{M}$-tensors. Theoretically, convergence theorems and comparison theorems are given, which show that the proposed methods are convergent, and the third one has the fastest convergence rate and performs better than the original Gauss-Seidel method and the one in (Calcolo, 57(2020) 15). Also, the monotonic theorem is studied. Finally, numerical experiments including some applications in the higher-order Markov chain and directed graph verify the correctness of the theoretical analyses and the effectiveness of the proposed methods, and illustrate that they are superior to the original Gauss-Seidel method and the preconditioned Gauss-Seidel methods in (Calcolo, 57(2020) 15) and (Appl. Numer. Math., 134(2018) 105–121).