Playing more Flow Free, I think I've realized why I'm so amazingly brilliant at this game:
The objective is to connect all pairs while covering the entire board, but in every puzzle there is always a unique solution connecting all pairs (even without the board-filling constraint).
So in a mathematical language, we are given $t$ pairs of vertices in an $n\times n$ grid, with the promise that there is only one collection of vertex disjoint paths that connects each pair, and furthermore, this unique collection covers the entire grid.
What is the complexity of this problem?
Update: I've realized that in the Hexagonal grid version game that I'm playing a unique solution practically (!) implies that the whole board is covered, so it's not really a big difference.