Let us call one arrangement of colours on the streets a colouring, and one selection of a square and the change of colours of all streets leading to that square a transformation.
Note that if we can get from one colouring to another by a sequence of transformations, then we can also get from the second colouring to the first one using that same sequence of transformations.
Therefore, the initial claim is equivalent to claiming that, if we start from a colouring where all streets have the same colour, there exists a colouring that cannot be achieved by any sequence of transformations.

In any sequence of transformations, we can assume that each square either does not appear or appears exactly once. Namely, if we perform an even number of transformations on some square, the result will be the same as if we did not perform any transformations, and an odd number of transformations will have the same result as if there was exactly one transformation.

Furthermore, note that in the sequence of transformations which are performed to get from one colouring to another, the order of the transformations is not important, i.e. it is only important to determine the set of squares included in these transformations.
The number of different sets of squares is $2^N$, since for each of the $N$ squares we can decide whether it is included in the set or not.

Note that the set where all squares are included leads to the colouring which is identical to the initial colouring, since we changed the colour of each street exactly twice. The same result can obviously also be obtained if we do not include any square in the set. Since those two sets lead to the same colouring, the number of different colourings that can be achieved from any initial colouring is not greater than $2^N - 1$.

We have two possible initial colourings (one where all the streets are red, and one where all the streets are blue), so the total number of colourings that can be achieved from an initial colouring is not greater than $2 \cdot (2^N - 1) = 2^{N+1} - 2$.

Since there are $M$ streets, and each street can be coloured in one of two possible colours (red or blue), the total number of possible colourings is $2^M$.

Since $M > N$, we have $2^M \ge 2^{N+1} > 2^{N+1} - 2$, so we can conclude that there exists a colouring that cannot be achieved from the initial monochromatic colourings. This completes the proof.