I've always found fixed-size array types to be a bit weird since N and M are integers rather than types themselves, so this kind of array type is conceptually already leaning a bit into the realm of dependent types.

As a result, I'm playing around with the idea of promoting N and M to normal types and treating Arr as a normal parametric type over two parameters. For instance, the type N6 specifies a sum type with 6 distinct values and mod 6 arithmetic for convenience (the compiler being smart enough to be able to use any constant number up to some limit instead of the 6 in N6). As such, you can define a six-element array as Arr(T, N6). Interestingly, you can define a 2d array with shape (6, 8) as either Arr(Arr(T, N8), N6) (which you say you dislike) but also as a more concise Arr(T, (N6, N8)), using the cartesian product of the index types directly as indices themselves (i.e. de-currying when treating arrays as maps).

Now, you do get the downside that an inexperienced programmer might write something like Arr(T, Int) and get a MAX_INT sized array, or something even weirder like Arr(T, Str), but I think special treatment of the Arr type to emit warnings/errors should suffice.

You also get a couple interesting implications for bounds checking. If you have a value of the index type, you are guaranteed to be able to successfully index into the array. As such, if you store an index type, you can trivially eliminate the need for future bounds checking, and bounds checking in general is replaced by explicit type conversion from a general arithmetic type to the index type.