We use the horizontal segments to pair up the inside points. Each inside point belongs to exactly one pair. Each column can contains at most $(n-1)/2$ pairs, hence there is at least one vacant cell ( that is, contains no $P_i$ ). Thus there are at least $n$ vacant cells in total. That gives $m \leq n^2-n$. Experimenting with small values of $n$ seem to suggest this bound is tight, but I dont have yet a construction for general case.

ninjaturtle wrote: Each column can contains at most $(n-1)/2$ pairs, What do you mean? I don't understand. For $n=6$, here is a path with $m=32$, only four 'unused' lattice points: [asy][asy] draw((0,1)--(1,1)--(1,2)--(2,2)--(2,1)--(3,1)--(3,2)--(4,2)--(4,1)--(6,1)--(6,2)--(5,2)--(5,3)--(6,3)--(6,4)--(4,4)--(4,3)--(3,3)--(3,4)--(1,4)--(1,3)--(2,3)--(2,5)--(1,5)--(1,6)--(3,6)--(3,5)--(4,5)--(4,6)--(5,6)--(5,5)--(6,5)--(6,6)--(7,6),linewidth(1));[/asy][/asy] EDIT: oops, I just realized that the problem is only asked for odd $n$. And now I see: you should have said "each row can contain at most $(n-1)/2$ pairs." For even $n$ it seems less regular. e.g. $f(8)$ seems much smaller than $56$.

You still have to pair up the points vertically ( using columns ). That is because the first and the last point do not pair up with any inside point horizontally. The restriction that $n$ is odd simplifies the problem greatly. I still dont know what the answer should be for general $n$.

Here is a construction to show that the upper bound for odd $n$ can be obtained, by induction from $n$ to $n+4$. $n=3$: [asy][asy] draw((0,1)--(1,1)--(1,3)--(2,3)--(2,1)--(3,1)--(3,3)--(4,3),linewidth(1));[/asy][/asy] $n=5$: [asy][asy] draw((0,1)--(1,1)--(1,2)--(2,2)--(2,1)--(3,1)--(3,2)--(4,2)--(4,1)--(5,1)--(5,3)--(4,3)--(4,5)--(3,5)--(3,3)--(2,3)--(2,5)--(1,5)--(1,4)--(5,4)--(5,5)--(6,5),linewidth(1));[/asy][/asy] $n-4\to n$: [asy][asy] draw((0,1)--(1,1)--(1,2)--(2,2)--(2,1)--(3,1)--(3,2)--(4,2)--(4,1)--(5,1)--(5,2)--(6,2)--(6,1)--(7,1)--(7,2)--(8,2)--(8,1)--(9,1)--(9,3)--(8,3)--(8,4)--(9,4)--(9,5)--(8,5)--(8,6)--(9,6)--(9,7)--(7,7),linewidth(1)); draw((3,3)--(2,3)--(2,4)--(1,4)--(1,5)--(2,5)--(2,6)--(1,6)--(1,7)--(2,7)--(2,9)--(1,9)--(1,8)--(3,8)--(3,9)--(4,9)--(4,8)--(5,8)--(5,9)--(6,9)--(6,8)--(7,8)--(7,9)--(8,9)--(8,8)--(9,8)--(9,9)--(10,9),linewidth(1)); [/asy][/asy] and in the middle comes the construction for $n-4$. There are only the four new points $(1,3),(n,2),(n-1,n-2),(2,n-1)$ which are unused, plus the $n-4$ unused ones in the middle by induction hypothesis, so altogether $n$ which yields $n^2-n$ used ones.

Here is my solution: We claim $m \leq n^2 -n$. Firstly, in each column there are at most $n-1$ points in it excluding the first and last columns, as each point must be paired with another one inside the same column. Note this same approach doesn't work if you consider points in rows, as the first segment $P_0P_1$ is horizontal and the last segment $P_mP_{m+1}$ is horizontal hence you can only obtain $m \leq n^2 - n +2$. My construction is the same as @above.

To prove that $m\leq n^2-n$ take the multigraph $G(V,E)$ where each collumn (from $1$ to $n$) is a vertex and we draw an edge between vertices $V_a$ and $V_b$ for each index $j$ such that $P_i$ is in collumn $a$ and $P_{i+1}$ is in collumn $b$. Draw two more vertices to represent $P_0$ and $P_{m+1}$. See that we have an eulerian path connecting $P_0$ and $P_{m+1}$ and thus the degree of each vertex is even, and therefore at most $n-1$. From this we conclude that $m\leq n(n-1)$ directly. The construction is the same as @above.