You may have to experiment a bit to find a paper and surface that takes the pencil in a way you like, but it should work fine. Prismacolor pencils have been around for a long time and have a great reputation.

I was talking with a monoprint maker the other day, and in the conversation we agreed that photographic paper (and prints) would make great plates for monoprints using water soluble media.