1. Open Wally and decals.wad.
2. Select the decal you want to edit.
3. Look at the color palette.
4. See that last color? I bet it's the color that the decal uses.
5. Go to Colors -> Edit Pallette...
6. Select the last color and double-click it.
7. Select a new color.
That's it! I haven't tested this myself yet but I think it works.