What are the possible sums of an $n \times n$ magic square? An $n\times n$ magic square summing to $S$ is an assignment of distinct integers to the $n^2$ entries of an $n \times n$ grid such that each row, column, and main diagonal sums to $S$.
It is well known that for $n>2$, an $n\times n$ magic square with sum $M_n=n(n^2+1)/2$ can be formed using the integers $1,2,\ldots,n^2$. Note that adding $c$ to each entry of such a magic square yields another magic square with sum $M_n +cn$; this implies that any sum that is $M_n$ modulo $n$ works. 
For $n=3$, it is easy to show that the sum must be 3 times the middle entry, and thus that the sum being $M_n$ modulo $n$ is both necessary and sufficient. But what about $n>3$?
 A: Here is a general construction based on the examples given by Bram28 and Ross Millikan, and comments by dshin.
Revised claim: for any integer $S$, an $n$ by $n$ magic square with sum $S$ exists for all $n\ge 4$.
To see this, first notice that there are two transformations that preserve the property of being a magic square: adding an integer constant $c$ to each entry (which increases the sum by $cn$, as already observed in the question), and multiplying each entry by a non-zero integer constant $d$ (which multiplies the sum by $d$, as noted in Bram28's answer).
Second, any set of $n$ squares in the $n$ by $n$ grid which has exactly one square in each row, column, and long diagonal, provides a set of locations which can be used to shift the sum of an $n$ by $n$ magic square.
Let's call such an arrangement a template.
Shifting the values in the locations determined by a template works as long as the values in the square differ from each other by a "large enough" value to avoid collisions with values used elsewhere in the magic square.
We need to make this second observation more precise.
There are $n$ by $n$ magic squares for each $n \ge 3$.
Hence to prove the claim, it is enough to construct a magic square for each $n \ge 4$ and to show how to modify it to obtain another magic square with the desired sum, based on a template.
To see that a template exists for $n=4$ or each odd integer $n \ge 5$, pick squares $(1,3),(2,2),(n,1)$ as well as the squares $(3,4),(4,5),\dots,(n-1,n)$ that are just off one of the long diagonals.
For even $n\ge 6$, pick $(n,1),(n/2-1,n/2+1),(n/2,n/2)$, as well as $(1,2),(2,3),\dots,(n/2-2,n/2-1)$ and $(n/2+1,n/2+2),(n/2+2,n/2+3),\dots,(n-1,n)$.
This choice of squares guarantees one square in each row and column, while the long diagonals are taken care of by $(2,2)$ or $(n/2,n/2)$ for the one diagonal and $(n,1)$ for the other, so it is a template.
(This construction seems to be a version of dshin's suggestion.)
Now start with any magic square with values $1$ to $n^2$ as outlined in the question.
There are two different constructions, depending on whether $S=0$ or $S\ne 0$.
First suppose $S=0$.
If $n$ is odd, then subtract $(n^2+1)/2$ from each value.
Otherwise $n$ is even, so multiply each value by $2$, and then subtract $n^2+1$.
Now suppose $S\ne 0$.
In this case, first multiply each entry by $2n^2S \ne 0$.
This intermediate magic square uses values $2n^2S, 4n^2S, 6n^2S, \dots, 2n^4S$; these all differ pairwise by at least $2n^2S$, and the square has sum $Sn^3(n^2+1)$.
Subtract $Sn^2(n^2+1)$ from each entry in the magic square, giving a magic square with sum $0$.
Now add $S$ to each of the entries that form a template.
Since the template contains precisely one entry from each row, column, and long diagonal, this results in a final magic square with sum $S$.
(I have removed my earlier suggestion using solutions of the $n$ queens problem, since the above construction is simpler and more general.)
