The original reason why Newton did that is that the only central force law (in terms of powers of r--and this might be valid for any function of r, but I'm not sure) that produces elliptical orbits for the planets with the Sun at the focus of the ellipse. So, it's basically the only option, to the extent that the orbits really are elliptical (which is really only a good approximation).
A linear force law also produces elliptical orbits, but then the Sun would have to be at the center of the ellipses, which is not what we see.
Newton's law of gravity was one of his greatest achievements because he was able to demonstrate these facts using Euclidean geometry. His proofs are complicated, but they are described in a somewhat readable form in Brackenridge's book, The Key to Newton's Dynamics (I say it's complicated, but it's possible to give a fairly simple outline of the main points, which is done in the first few chapters--unfortunately, I am too rusty on it to describe it here, and I never found the time to finish the rest of the book).There may also be other explanations for the r^2 (I saw one in a book about quantum field theory, and you could derive it as some sort of limiting case in general relativity).