We report molecular simulations using a relatively soft interatomic potential to determine the nature of melting under extreme conditions. At temperatures and pressures above the triple point of normal materials, the density range of two-phase solid and fluid equilibria is bounded by freezing and melting curves. We address the unresolved issue of the termination of these boundaries, i.e., whether the melting curve of a solid terminates in a critical point, exhibits a maximum, goes to an asymptotic limit, or continues indefinitely. Significantly, we observe a negative change in volume upon melting at high pressures, which is normally observed only for water. We provide unequivocal evidence that the densities of the meeting and freezing lines can merge at a melting temperature maximum point. This could be a general feature of "soft" atomic fluids at extreme pressures.