1. Understanding the Problem:
We need to fill an $n \times m$ grid with tokens starting from $M$ initial tokens placed in $M$ empty cells. The rule for placing a token in an empty cell is that it must share a common side with at least two other cells that contain a token. We need to find the minimum value of $M$ in terms of $n$ and $m$ that allows us to fill the entire grid.

2. Analyzing the Grid:
- Each boundary row and column must contain at least one token.
- Consider the bottom row. There must be at least one token in this row, say $T_1$.
- If there are no tokens in the two rows above $T_1$, we cannot fill the grid. Therefore, there must be at least one token in these two rows.
- To minimize the number of tokens, this token should not be in the adjacent row to $T_1$. If this token is not in the same column as $T_1$, we cannot fill the grid. Hence, these two tokens must be in the same column.

3. Minimum Tokens in a Column:
- Continuing this logic, there must be at least $\left\lceil \frac{n}{2} \right\rceil$ tokens in this column.

4. Minimum Tokens in a Row:
- Similarly, for columns, there must be at least $\left\lceil \frac{m}{2} \right\rceil$ tokens in some row.

5. Combining Rows and Columns:
- Since a column and a row can coincide in at most one square, we must have at least $\left\lceil \frac{m}{2} \right\rceil + \left\lceil \frac{n}{2} \right\rceil - 1$ tokens.

6. Special Cases:
- For $n$ and $m$ both odd, we can provide an example with $\left\lceil \frac{m}{2} \right\rceil + \left\lceil \frac{n}{2} \right\rceil - 1$ tokens. Place one token in the top right corner and start placing tokens in the first row and first column such that each token is placed in a square 2 columns/rows away from the last token placed in that column/row. This configuration works.

7. Even Dimensions:
- If $n$ is even, a column has at least $\left\lceil \frac{n}{2} \right\rceil$ tokens, leaving one boundary square without a token. If we do not place an extra token in this square, the column with $\left\lceil \frac{m}{2} \right\rceil$ tokens must go through this boundary square, making it impossible to fill the grid with $\left\lceil \frac{m}{2} \right\rceil + \left\lceil \frac{n}{2} \right\rceil - 1$ tokens. Therefore, we need $\left\lceil \frac{m}{2} \right\rceil + \left\lceil \frac{n}{2} \right\rceil$ tokens.

The final answer is $\boxed{ \left\lceil \frac{m}{2} \right\rceil + \left\lceil \frac{n}{2} \right\rceil }$ if one of $m$ or $n$ is even, and $\left\lceil \frac{m}{2} \right\rceil + \left\lceil \frac{n}{2} \right\rceil - 1$ otherwise.