Just a hint from my extensive experience from self balancing robots:

• The most important aspect of a self balancing robot, is the actuator acceleration (torque) control.

(...) the motors start rotating at the maximum speed (PWM: 255) and the robot still doesn't seem to recover back and just keeps running and then finally falls down in the direction in which it was moving. It doesn't seem to recover at all.

Because to balance, the robot needs shifts in velocity, i.e. acceleration (produced by motor torque). If your motor saturates, the control cannot execute the balancing action: accelerate to shift the center of mass.

Furthermore, the relationship between the tilt angle, and the required motor acceleration is not linear. i.e. to recover from 5 deg may require 0.1 N.m from the motors, and to recover from 7 deg may require 1.0 N.m.

Would implementing the PID feedback for encoders as well solve this issue?

You definitely should have PID for motor control. How do you make sure the motors are performing the velocity/torque that the balancing PID requested?

I'm planning to use cascaded PID controllers in which the encoder PID measures the error in position and its output will be the set-point for the angle PID loop which in turn will control the PWM of the motors.

Yest, looks good! See similar question: Self balancing robot control system strategies

Just a hint from my extensive experience from self balancing robots:

• The most important aspect of a self balancing robot, is the actuator acceleration (torque) control.

(...) the motors start rotating at the maximum speed (PWM: 255) and the robot still doesn't seem to recover back and just keeps running and then finally falls down in the direction in which it was moving. It doesn't seem to recover at all.

Because to balance, the robot needs shifts in velocity, i.e. acceleration (produced by motor torque). If your motor saturates, the control cannot execute the balancing action: accelerate to shift the center of mass.

Furthermore, the relationship between the tilt angle, and the required motor acceleration is not linear. i.e. to recover from 5 deg may require 0.1 N.m from the motors, and to recover from 7 deg may require 1.0 N.m.

Would implementing the PID feedback for encoders as well solve this issue?

You definitely should have PID for motor control. How do you make sure the motors are performing the velocity/torque that the balancing PID requested?

I'm planning to use cascaded PID controllers in which the encoder PID measures the error in position and its output will be the set-point for the angle PID loop which in turn will control the PWM of the motors.

Yest, looks good! See similar question: Self balancing robot control system strategies