Why does camera this tracking fail completely even when the solution value is very low?
For this kind of shot, where the camera hardly moves I don't think you're going to get good results using motion tracking. 

There is so little parallax information for the reconstruction.

For a detailed post on motion tracking read:

How can I get better results when doing camera motion tracking?

I'd suggest you stabilize the footage as if it was a fixed shot and then do the reconstruction using BLAM ( https://github.com/stuffmatic/blam ).


  NOTE: Blam is no longer mantained and has been replaced by Fspy: https://fspy.io/, but there is no importer for blender 2.79 or previous versions.


For a detailed post on how to use blam and Fspy read: How can I recreate geometry using a photograph?