I would begin by removing all of the access panels so that you can reach the step/belt. there should be a main connecting link much like a master link on a timing belt. Remove the master link and you should be able to pull the step/belt out using a bobcat or a chain pull setup. Once you have the sep removed, the majority of the remains will be structural framework that you can either torch cut or cold cut depending on the surrounding environment. I f torches are used take care to not ignite the lubrication materials that will be present (grease, nylon pads etc.)
As far as cost, I wouldn't want to quote anything without either seeing it up close or at least seeing pictures of the escalator and the surrounding environment.