There were essentially two things that allowed him to reach this conclusion, if not very robustly.

• Having derived his law of universal gravitation, Newton knew that a perfectly spherical body would cause an equal gravitational acceleration at all points on its surface; this is self-evident. Now, one may easily note the discrepancy in gravitational acceleration by comparing the lengths of pendulums made for clocks at different latitudes (a French astronomer, Jean Richer, had found this in the early 1670's).

• There are two ways for this discrepancy to arise. The centrifugal acceleration due to the Earth's rotation could be strong enough to counteract the gravity, and/or Earth could be deformed by the acceleration. Knowing the acceleration difference and Earth's radius, we can easily do a first order calculation using the centripetal acceleration formula a = v^2/r. Plugging in the numbers 1600 km/h and about 6300 km, we find an acceleration of about 0.03 m/s^2. That's of the right order, but only half of the difference between acceleration at the poles and at the equator. To get the rest of the difference, which is about 0.3% of the total acceleration, we may use the inverse square form of Newton's law to find that a deformation that extended the radius by no more than about sqrt(1/0.997)-1 = 0.15% is needed to account for the rest of the deviation, which seems plausible enough (it's a slight overestimate, as it turns out). Newton had taken note of the fact that flattening of the poles had been observed on Jupiter (a gas giant) and so he proposed that Earth, which he assumed to have been in an initially homogenously fluid state, deformed due to its rotation, completing his explanation.

This seems like a simple enough conclusion in hindsight since we know he answer, but Newton had to make quite a few assumptions to get there. The argument does not quite hold if we suppose that the Earth could be deformed about an axis that is not its axis of rotation, for example, or that it isn't homogenously dense, or any number of other complications. However, Newton seems to have relied on his first intuition here and his argument was thus relatively simple. For a very indepth treating of the history of this problem and how to make more rigorous approaches than that of Newton, see The Problem of the Earth's Shape by John Greenberg, particularly chapter I, which I draw on here for the historical aspects. The calculations/estimates above are my own based on first approximations of standard data.