Melting properties are critical for designing novel materials, especially for discovering high-performance, high-melting refractory materials. Experimental measurements of these properties are extremely challenging due to their high melting temperatures. Complementary theoretical predictions are, therefore, indispensable. One of the most accurate approaches for this purpose is the ab initio free-energy approach based on density functional theory (DFT). However, it generally involves expensive thermodynamic integration using ab initio molecular dynamic simulations. The high computational cost makes high-throughput calculations infeasible. Here, we propose a highly efficient DFT-based method aided by a specially designed machine learning potential. As the machine learning potential can closely reproduce the ab initio phase-space distribution, even for multi-component alloys, the costly thermodynamic integration can be fully substituted with more efficient free energy perturbation calculations. The method achieves overall savings of computational resources by 80% compared to current alternatives. We apply the method to the high-entropy alloy TaVCrW and calculate its melting properties, including the melting temperature, entropy and enthalpy of fusion, and volume change at the melting point. Additionally, the heat capacities of solid and liquid TaVCrW are calculated. The results agree reasonably with the CALPHAD extrapolated values.