They don't have to be higher-end hotels. I've sent luggage from the APA Hotel Narita (featuring the world's smallest rooms), Tokyu Stay, and some obscure ryokan in Nara whose name I forget. I have vague memories of a non-chain business hotel telling me that I had to send my suitcase from the kombini, but that was a long time ago.

The hotels that offer this service do not charge extra. The front desk personnel do it as part of their job. It's helpful to have a business card or a printed out webpage from your next hotel so that the desk clerk knows the proper way to write the address in Japanese script. Place names, especially the names of local districts and neighborhoods, may be written with any one of several combinations of kanji that sound alike, or they may be written with kanji that make no sense at all.

Furthermore, any hotel will receive a future guest's luggage. Sometimes it's behind the desk when I arrive. In a few cases, the desk clerk says, "It's already in your room."