 Solution

A simple square-lattice polygon has even perimeter at least four. Generate a self-avoiding walk of length $M-1$, reject unless its endpoint is a neighbour of the origin, then add the final edge to close it.

sap <- function(M) {
  stopifnot(length(M) == 1L, is.finite(M), M >= 4,
            M == floor(M), M %% 2 == 0)
  repeat {
    path <- saw(M - 1L)
    if (sum(abs(path[nrow(path), ])) == 1L) {
      return(rbind(path, c(0L, 0L)))
    }
  }
}

The output has $M+1$ coordinate rows and $M$ unit edges. The first $M$ vertices are distinct by the call to saw; the last row repeats only the origin. Neighbouring lattice edges cannot create an additional crossing without a repeated vertex. A rectangle of perimeter $M$ exists for every permitted even $M$, giving a positive probability of eventual acceptance.