How much background material should a mathematical research paper include?
I'd recommend putting in as much explanation, context, and background as you reasonably can.  In principle you could certainly put in too much, but in practice I don't think I've ever seen a mathematics paper I thought actually did have too much.  If you structure your writing so experts can easily skim things they already know, then I don't see why extra explanation should trouble anyone.  Tradition requires being concise, but that tradition was based on the economics of publishing.  Space in printed journals used to be a scarce resource, and if you spent it on unnecessary exposition you were keeping someone else from publishing at all.  Publishing still isn't free (and readers have only so much patience, as well), so you shouldn't include enormous amounts of unnecessary background, but traditional writing styles should be adjusted to account for the greater availability of space.

It's possible that a referee or editor will object that they don't like your style.  You may be able to resist making any changes (it depends on how exciting your paper is and how high your own status is within the community), and if you do make changes you can still keep a lot of explanation.

If necessary, it's worth having two versions as Paul Garrett suggests.  If you do, then you should make it very clear which is which and what the differences are, to avoid serious confusion if someone refers to the paper without realizing they need to specify which version.


  The background material is "standard" in the sense that anyone who works on this class of problems would know the definitions or results in some form. However, this is at most a few hundred people, while if I include the background material my paper should be comprehensible to an advanced undergraduate.


One reason to be generous with explanation is that it's easy to overestimate how much people know.  Aiming at advanced undergrads is a good way to make sure grad students really can read the paper.  If you aim at experts, you may write a paper only your own collaborators can comfortably read.


  Some of the background results are part of the folklore of the field, and I've never been able to find a proof of them in literature. While they are believable and not hard to prove, I feel someone should bother doing it.


This is a great reason to include a proof, although it's important to consult with experts to confirm that there really isn't an accessible proof in the literature.


  It makes the paper longer, although even with the background the paper is not long (13 pages).


You should make sure it doesn't look like padding, say with just a few pages of original content among the 13 pages.


  From what I've heard, it is generally considered bad practice to restate definitions and constructions states elsewhere and to reprove theorems available in literature. In part this is because it gives the impression that I haven't read the literature.  This is exacerbated by the fact that I only cite ~5 previous works, mostly for further reading or alternative presentations of some of the background.


This does seem like a worry, and five references is not very many, even for a 13-page paper.  You might not strictly need any more, but I'd recommend tracking down additional references for background.  As a general rule it's best to cite generously, giving plenty of credit to other authors and offering many resources to readers.

Regarding giving the impression that you haven't read the literature, it's important to be clear about what's background from the literature (with a citation), what's folklore, and what's your own contribution.  If you reprove something you say is known but don't give a citation for, it can look like you were too lazy to track it down.