I know this is an old post, but just in case anyone else stumbles across this I found a property in the refiner web part that was the culprit. Now I will caveat this with saying I am currently working on SharePoint 2016, but the refiner control and code doesn't appear to have been changed since SP13.
We are working with a large dataset (1.7 million records) and when the results were still in hudreds of thousand, the refiners were off. When searching and refining the results so that they were at a smaller count (< 100,000) the refiners were playing nice, which got me thinking.
So I exported the Refiner web part and under the "SelectedRefinementControlsJson" property, for each refiner added, there was a "deepHits" attribute set at 100000 (100,000). As soon as I made higher, or in my case I added a zero to maek it 1000000 (1,000,000), the results started returning correctly. Even at for refiners over 1,000,000 mark they now show correctly.
Before Fix

After Fix
