Using divisibility relations between the generators of a square-free monomial ideal $I$, we describe divisibility relations between the generators of the second power $I^2$. We then employ discrete Morse theory to produce a cellular free resolution of $I^2$ which is minimal for specific ideals that are extremal with respect to a given divisibility relation. In particular, we provide sharp bounds on the projective dimension of $I^2$ when the generators of $I$ satisfy at least one divisibility relation.