  Magnetic frustrations and dimensionality play an important role in
determining the nature of the magnetic long-range order and how it melts at
temperatures above the ordering transition $T_N$. In this work, we use
large-scale Monte Carlo simulations to study these phenomena in a class of
frustrated Ising spin models in two spatial dimensions. We find that the
melting of the magnetic long-range order into an isotropic gas-like paramagnet
proceeds via an intermediate stage where the classical spins remain
anisotropically correlated. This correlated paramagnet exists in a temperature
range $T_N < T < T^\ast$, whose width increases as magnetic frustrations grow.
This intermediate phase is typically characterized by short-range correlations,
however the two-dimensional nature of the model allows for an additional exotic
feature -- formation of an incommensurate liquid-like phase with algebraically
decaying spin correlations. The two-stage melting of magnetic order is generic
and pertinent to many frustrated quasi-2D magnets with large (essentially
classical) spins.
