We show that a system of particles interacting through the exp-6 pair potential, commonly used to describe effective interatomic forces under high compression, exhibits anomalous melting features such as reentrant melting and a rich solid polymorphism, including a stable BC8 crystal. We relate this behavior to the crossover, with increasing pressure, between two different regimes of local order that are associated with the two repulsive length scales of the potential. Our results provide a unifying picture for the high-pressure melting anomalies observed in many elements and point out that, under extreme conditions, atomic systems may reveal surprising similarities with soft matter.