The unit does not have to be in their territory in order to gift it. Aside from the method GoatRider mentioned, you can go to the City-State's diplomacy screen, and then click on "Gift Unit." When you click on the unit you would like to gift, you should receive a confirmation asking "Do you want to give [city] your [unit]?" and an option to choose "Yes" or "No." If you choose yes, it takes three turns for the unit to reach the city-state itself.
You're apparently not receiving the pop-up confirmation. This may be a silly question, but are you sure that the unit you are clicking on to gift belongs to you? When you click on Gift Unit and your cursor changes, the hex of any units that you have eligible to gift will become outlined in yellow.
In addition, doing some testing here, it seems that you cannot gift Workers or Great Merchants (I'm not sure about other Great People as that was the only one I had to test with). If I tried with either of those, I had the same problem you did. I think perhaps combat units are the only ones eligible.