Deciding on M will probably depend on the context. Increasing your sample size comes at some cost (otherwise you would just use the entire population). You need to weigh that cost against the cost of getting a wrong answer, which becomes increasingly likely with lower levels of precision in your estimate. A way to help think about this is to attach different decisions you might make depending on what estimate of P you find. In the extreme let's say you would do something radically different if P = .51 than if P = .49. In this case, you would want a very precise answer.
But at the very least you could plot M as a function of sample size and proportion to get some idea of the possibilities. In R...
power <- list()
i <- 1
for (p in seq(.01, .99, .01)){ # Proportions
for (n in seq(5, 1000, 5)){ # Sample sizes
m <- (1.96) * (sqrt((p * (1 - p))/n)) # Solve for m
power[[i]] <- c(p, n, m) # Stick it all in a list
i <- i + 1
}
}
power <- as.data.frame(t(do.call(cbind, power))) # Convert list to useful DF
colnames(power) <- c("P", "N", "M")
library(ggplot2)
ggplot(power, aes(x = P, y = N, fill = M, z = M)) + # Level plot with ggplot2
geom_tile() +
stat_contour(breaks = c(.1)) + # Use contour to identify level(s) of M you might want
ylab("Sample Size") +
xlab("Proportion") +
scale_fill_gradient(name = "ME", limits = c(0, .45),
low = "white", high = "red") +
scale_x_continuous(expand = c(0,0)) +
scale_y_continuous(expand = c(0,0)) +
ggtitle("Figure X. Margin of error\nas a function of sample size and proportion.") +
theme(plot.background = element_rect(fill = "white"),
strip.background = element_rect(fill = "white"),
text = element_text(color = "black", family = "mono"),
axis.text.x = element_text(color = "black"),
axis.text.y = element_text(color = "black"),
plot.title = element_text(hjust = 0))

Formula for SE from here.