You will find plenty of transformers at
www.digikey.com. They aren't the cheapest by any means but it is easier to find stuff there and easy to make small orders.
If 0.22A@117V is enough, here is one for $15:
http://search.digikey.com/scripts/DkSearch/dksus.dll?Detail&name=237-1269-ND
Price of a transformer will vary a lot depending on how much power you need.
If you are just driving a relay and don't need much current, you probably don't need a full transformer, you can use an autotransformer (non isolated).
Any transformer with sufficient wattage and a split 110V/220V primary can be wired as an autotransformer. If you have any surplus transformers around, this is worth considering. Just insulate over the secondary leads and connect the two windings of the primary in series and wire the relay across one. The voltage won't be exactly half, but it may be close enough (you can even use the secondary for boost/buck if necessary).
http://en.wikipedia.org/wiki/Autotransformer
Radioshack has a $50 step down transformer (not in stores, though):
http://www.radioshack.com/product/index.jsp?productId=2285470&filterName=Category
Depending on your relay specs, a replacement 220V relay might be cheaper, but probably not (220V coil relays are a bit expensive).
It is also possible to rewind a relay coil for 220V or 110/220V operation if the relay is easy to disassemble. Unwind the old coil, counting the turns and measure the diameter of the bare wire with a micrometer. Order a spool of magnet wire with 0.707 times the diameter (look up in a wire gauge table) and wind twice as many turns as were originally present for 220V. For 110/220V, wind two coils with the original number of turns and connect them in series for 220V and in parallel for 110V. Use sandpaper to strip the insulation off the ends. A piece of 1/8" or 1/4" threaded rod (if that is a suitable size to fit through the bobbin) with some nuts to hold the bobbin in place run through a hole in a piece of wood (clamped in a vice) as a bearing and bent into a crank shape will do for a coil winder. A pair of nuts on each side of the bobbin and a pair with washer on each side of the block of wood. It doesn't hurt to wrap a little tape around the threaded rod to match the inner diameter of the bobbin. Here is another DIY coil winder from a hand cranked drill with a pedometer modified as a turns counter:
http://www.instructables.com/id/DIY-Hand-Driller-Coil-Winding-Machine-with-Digital/
There are a bunch of coil winding videos on youtube, etc.
http://video.google.com/videosearch?q=DIY+coil+winder#
Wind the coil evenly so you can fit the same amount of wire in the same space. First layer right to left, second layer left to right, third layer right to left, etc. If you hold the wire slightly to the left when winding right and slightly to the right when winding left it will automatically wind each turn next to the previous one without a gap. It helps to put the spool of wire on a horizontal shaft so it can unwind as needed and you can tension and guide the wire between your finger and thumb. Note that for a 220V coil you may be using rather fine wire which will snap with too much tension; don't let the wire tangle coming off the spool.
One of many sources of magnet wire (ebay/froogle for more).
http://www.allspectrum.com/store/index.php?cPath=85_251&osCsid=8bef21eb670a4167a37b1bd0e7721d6e
Table of wire gages including feet per pound for magnet wire:
http://www.mwswire.com/pdf_files/mws_tech_book/copper_magnet_wire_data.pdf
with recomended tension:
http://www.elektrisola.com/us/magnet-wire/technical-data-by-size/nema-mw1000c.html
Polarity matters when connecting series/parallel windings.