It could be because your soft tonneau cover added drag instead of reducing it. You could replace it with a hard-folding tonneau cover instead. 4wheelonline has a good selection of bed covers. Check them out.
I traded 2000 Frontier CC for 2005 F150. Put a Lund soft cover over the 6ft box. Mpgs went from 17 to 14-15!! Then opted for a used top of the line glasstite topper. Back to 16, even squeezed a 17mpgs on long trip! My 2014 Frontier CC has gotten 16, even 17 with a ARE glass topper. Again on a trip to Upper Michigan, driving 55 to 60, got 21mpgs on a couple tanks! Never driven anywhere without the topper yet,so don't know if it can get the 21 the sticker claims!