I had to find another video too see the gameplay in action.
http://www.youtube.com/watch?v=9ueT5A-ckDY
[edit]
I just watched more of the video and it looks like the characters do scale slightly along the z plane. So I am now leaning toward the fact that this may have been done 3d.
At first I was thinking multiple layer tile engine 2d, but looking closely at the characters they are able to move closer/further very smoothly without looking like there are preset layer paths.
I am thinking that if you want it to play exaclty like that it may be easier to just do it in 3d.
good luck!
"When I look at that square... I wish FPSC noobs would stay on their side of the forums and stop polluting these boards." - Benjamin