From the box I thought it was some kind of Rampage sequel / successor, and looking at the gameplay it looks like it kind of is!
It’s like Rampage meets Barbarian.
These kinds of games always remind me of It Came From The Desert on The Amiga. Which always reminds me of some indie remake that got stalled in development. After a bit of googling it turns out to be “They Came From Hollywood”, which it looks like I most likely first learned about on QT3!