It's not a timed mission -- the Palace health meter goes down as it takes damage from RPGs and tanks. Make sure to kill any RPG wielding enemies first before taking down anyone else (except when you're shooting at tanks). You'll hear one of your buddies yell "RPG!" and you'll see an enemy with a big green arrow over his head. One thing I found effective is using your healthy supply of grenades to take out the RPG guys, which game me more time to shoot at everyone else.
I've been playing on hard from the beginning and taking my time, so I just finished that level. I should warn you: level 5 is also pretty tough.