Can a more powerful encoding of an input make an algorithm that is polynomial in the number of inputs become exponential?
There are $2^{n^2}$ labelled directed graphs on $n$ vertices.  Therefore, any such graph requires at least $n^2$ bits to represent it.  So, there is no hope for an encoding scheme that always uses at most $O(\log n)$ bits and can encode all graphs.

If you want to focus on labelled directed graphs with $n$ vertices and $m$ edges, there are ${n^2 \choose m}$ of them, which for $m \ll n^2$ is approximately $(e n^2/m)^m / \sqrt{2\pi m}$, and thus you'll need at least $m \lg (n^2/m) + O(m)$ bits to represent all of them.  Notice that this is $\Omega(m)$, so there is no hope for an encoding scheme that uses only $O(\log m)$ bits (or $O(\log(m+n))$ bits) and can represent all such graphs.

Of course, you can consider encodings that are logarithmically short, but they can only express a tiny fraction of all possible graphs.  Yes, if you wanted to represent the input in that way and solve a reachability problem on such a graph, then ordinary DFS would take time exponential in the size of the input.

Related: You might be interested in succinct data structures.