Probability for an element to appear in at least one set
For very crude bounds, you could use Chebyshev's inequality.

Let $x$ denote one (fixed) value from the set of $M$ possibilities.  The probability that $x$ appears at least once in the union of the sets is something like

$$p = 1 - \left({{M-1 \choose N} \over {M \choose N}}\right)^k.$$

Now if we let the random variable $X$ denote the number of elements that appear at least once in the union of the sets, we can use linearity of expectation to get that $\mathbb{E}[X] = Mp$.  You should be able to compute $\text{Var}[X]$ using similar methods.  Then, you should be able to use Chebyshev's inequality to bound the probability that $X$ is far away from its expected value.

This will give a pretty weak bound, so it's unlikely that this is the best approach.  Hopefully others will suggest better methods.