With tabular reinforcement learning (RL) methods, then catastrophic forgetting does not come into play, as it is a feature of online learning with approximators such as neural networks. Essentially your table never forgets anything, although it may become out of date for rarely-visited state/action pairs whilst an approximator will often still maintain them at least a little due to generalisation.
The convergence time for RL methods is highly variable, and depends on many factors.
Tabular methods have relatively simple requirements for state/action visits though, and if your two environments are very similar, then it might be reasonable to expect the amount of experience required for convergence to scale roughly according to $O(|\mathcal{S}| \times |\mathcal{A}|)$ - that assumes you have no guiding principle to generalise state/action features or skip explorations.
Assuming your convergence sample size really is $O(|\mathcal{S}| \times |\mathcal{A}|)$ then extrapolating from your smaller to your larger environment implies you may need as many as 50 million iterations to get convergence on the larger instance. This is a crude aprpoximation, because so much depends on the nature of the changes - it may be that 5 million should be enough (and something is wrong with your implementation), or you may need 500 million. For instance one important factor I have left out of very similar is episode length (assuming you are solving for an episodic problem) - if that is also significantly larger, you may be looking at the 500 million case. Also critically important is how long the initial agent takes to find high scoring episodes.
I also want to add that in this case there are state dependent actions, so for actions that cannot be taken I have created a dummy state and a negative reward. Is it the reason?
Ideally you would not allow the agent to take actions that are not possible in a current state. You should check your library in case there is a way to inform the agent of its current set of actions instead of specifying an action space for the whole environment. If there are a lot of unavailable actions, it could be costing the agent a lot of time exploring them and learning not to take them.
Instead of adding "dummy" states, one approach would be to give a negative reward and have the agent transition to its current state - i.e. no change. The negative reward should be larger than any negative reward possible for valid action choices (otherwise the agent may prefer to collect the slightly-less-negative reward than it predicts it will get from taking a real action).
There are lots of changes you might consider to improve your agent to deal with harder-to-solve environments in reasonale time. I am not sure what you are able to consider, so here are a few open-ended ideas:
Use function approximation to generalise state and action features. This does expose you to a whole different set of complications though, such as losing guarantees of convergence, and also catastrophic forgetting.
Use eligibility traces and either Q($\lambda$) or SARSA($\lambda$). This can help you find a sweet spot for learning efficiency by considering multiple trajectory lengths for estimating returns. Alternatively, you could consider n-step returns.
Use an experience replay table, or Dyna-Q with Q-learning, to extract more data from previous experience. Whether or not this is useful depends on how fast the environment simulation runs. If your learning time is limited mostly by simulation speed of the environment, this is a good choice. If it is limited by the time taken by the Q-learning process, you are better off generating fresh data as fast as possible.
