Complexity for single-linkage clustering with max norm
Single-linkage clustering gives the same connections in the same order that you would find using Kruskal's algorithm for the minimum spanning tree, and the clustering can be found by finding a minimum spanning tree and then running Kruskal's algorithm on the resulting $(n-1)$-edge graph. Therefore, the time is bounded by the MST construction + the time to sort the edges of the MST.

The two-dimensional $L^\infty$ MST can be constructed in $O(n\log n)$ time using rectilinear Voronoi diagrams, and an $O(n\log n)$ algorithm for the three-dimensional version is given by

Krznaric, Drago; Levcopoulos, Christos; Nilsson, Bengt J. (1999),
Minimum spanning trees in $d$ dimensions,
Nordic J. Comput. 6 (4): 446–461. 

more generally an algorithm that is within a polylog factor of linear for any fixed dimension is given by

Gabow, Harold N.; Bentley, Jon Louis; Tarjan, Robert E. (1984), Scaling and related techniques for geometry problems, Proc. 16th ACM STOC, pp. 135–143, doi:10.1145/800057.808675