Can you interpolate with QLearning or Reinforcement learning in general?
Since the convergence of QLearning is so slow I am wondering if it is possible with QLearning to interpolate the QValue of unexplored states since QLearning does not use a model?


When Q learning is described as "model free", it means that the agent does not need access to (or use) a predictive model of the environment. It cannot refer to state transitions and rewards in advance, but has to experience them in order to learn. 

This does not mean that you have to avoid using a learning data model (such as a neural network) in order to generalise to new unseen data. 

So, yes, Q learning can interpolate from unseen states and predict their Q value. To do this, you replace the state/action table with a supervised learning method based on descriptions of state $s$ and action $a$ as inputs, that you train as a regression model to predict $Q(s,a)$ (as a variant you can also have just state as input and predict $Q(s,a)$ for all possible actions as a vector in one go).

However, Q learning with a neural network suffers from instability. See Deep Mind's DQN paper for example of a system that solves that instability. In short:


Use experience replay - store S, A, R, S' data for each step and run the Q learning update on random mini-batches of the stored data, instead of online.
Keep two copies of the Q estimator neural network. Train one continuously, and copy it to a "frozen" version every now and then (e.g. every 100 mini-batches). Use the "frozen" copy to calculate the new $Q(s,a)$ targets.


This still might not match your learning scenario. If you want to solve mazes, think carefully about what data is truly available to the agent and how you might use it. For instance if you are using Q learning to solve a maze where you have a map, it is very inefficient approach. This is often shown as a toy problem, because it is possible to view the learning data very easily. But in that toy problem, the agent is not given the map, nor any knowledge of what a grid is.

Here are a couple of suggestions that may still help, separate to using a neural network value estimator:


If you do have a model of your environment (but not a map or other data that could be directly analysed for a solution), joining Q learning with a planning algorithm might work better for you than Q learning, as in Dyna-Q. This is relevant where you have an agent exploring in real time that would benefit from "looking" ahead before taking actions.
If your problem is very sparse rewards (due to larger maze, and only getting different reward at the end), then a worthwhile improvement is to look into multi-step TD learning, where the rewards are propagated back to previous steps more efficiently. Maybe look into $Q(\lambda)$