The naïve method you describe (loop over all points, select those that have more than $n$ other points within distance $M$ of them) is actually not a bad choice, as long as you store your points in a suitable spatial data structure (such as something based on a quadtree) that makes finding and/or counting nearby points a cheap operation. One advantage of this approach is that it will let you vary your definition of a cluster (e.g. to something like "the $n$-th nearest point is less than $f(n)$ distance away") fairly easily without having to switch to a different algorithm or a different data structure.
That said, for the specific definition you give, you don't really need a quadtree. The simplest spatial data structure sufficient for finding clusters according to your definition is just a regular grid.
As you note in the comments, simply dividing the map into a grid of squares (or triangles or hexagons) and binning each point into the square it's located in could fail to correctly detect clusters located near a grid boundary. However, the solution is simple: just count points located near a boundary in both of the squares on each side of the boundary.
In fact, if you make your grid consist of squares with a side length of (at least) $M$ units, you can use the following simple binning algorithm:
- For each point, find the location of the closest grid intersection (i.e. the closest corner point between four grid squares). You can do this with simple division and rounding of the point coordinates. Then add the point to each of the four grid squares touching the intersection.
- Once all points have been binned, look for squares with $n$ or more points. Not all such squares will necessarily contain a cluster according to your definition (and they might also contain several disjoint clusters), they are at least "weakly clustered" in the sense of having $n$ or more points at most $2\sqrt2 M'$ units apart (where $M' \ge M$ is the side length of your grid squares). What is guaranteed, however, is that all the points in any cluster with diameter at most $M$ are assigned to at least one common grid square.
In fact, for data visualization, you might not even need to find the actual clusters — it might be sufficient to plot the number of points assigned to each grid square by the algorithm above.
Note that, if your map is very large compared to your cluster diameter $M$, and your points are sparsely scattered on it, it may be inefficient to store the entire grid as a dense matrix or array. Instead, use a sparse array data type so that you only need to store data for squares that actually have points assigned to them. (This will also save time in the second step, since you can only iterate over the squares that actually have something in them.) You can also save a bit of storage space if you, instead of assigning each point to four adjacent squares, actually assign it to only one of them, but then, in the second step, look for groups of four adjacent squares with $n$ or more points.