Why does branching decrease density and melting point?
I'm not sure that your statement about density is always correct. Looking at octane and its isomers the density changes very little, for example

octane           $703~ \pu{kgm^{-3}}$ 

2-methylheptane  $698~ \pu{kgm^{-3}}$

2,5-dimethylhexane  $694~ \pu{kgm^{-3}}$

2,2,4-trimethylpentane  $692~ \pu{kgm^{-3}}$

although the melting points do change considerably. In the same order as above they are $-57, -112,-93,-107$ so octane is the exception here; (data from Wikipedia pages).

This can be explained by the fact that melting can be considered to be governed by the repulsive part of the intermolecular potential this having a greater influence than the attractive part when the molecule has an odd shape. Rod like octane has to have deeper intermolecular potential than the odd shaped isomers as it has a higher melting point. 

In the isomers the interaction should be dominated by the repulsive part of the potential as the odd shapes must try to push methyl groups into to one another. The potential itself has the same overall geometry, i.e. similar intermolecular minimum distance, as density is the same in all molecules above, but is shallower in nature due to the extra repulsion. Hence the isomers have significantly lower boiling points than octane.