Recommedation of budget hotel

My gal and I are going Japan this Dec for holiday. We are Singaporeans This is my 3rd time to Japan. Trip is 11days (Osaka/Kyoto/Shinjugu). Looking for recommendation of budget hotels less than 8000yen per night location near (Walking 8min) JR Osaka and JR Shinjugu station. Tried Rakuten and asiarooms websites. We do not mind sharing a single room bed just for our budget. But must come with attached bathroom/toilet.

Please help.

try www.japanhotel.net
they have both cheap hotels and more expensive ones. the cheapest are usually farther away from the stations (do you mean Shinjuku by the way?) . you may find hotels in other areas than Shinjuku too. any station on the Yamanote loop line is convenient as you can go anywhere in Tokyo. Please note that in Japan as in most countries (USA, Europe etc.) a single is for one person only. No exceptions.

For kyoto you can try http://www.kyotojp.com
They are really cheap and walking distance from JR kyoto stn.

In tokyo (assuming you said shinjuku), why don't you try staying in ueno, ikebukuro or nipponbashi area, i think the rooms are cheaper than those in shinjuku.

why don't you try looking in hostel booking sites like http://www.hostels.com or http://www.hostelz.com
http://www.hostelbookers.com
http://www.tokyohostels.com/
Some hostels have rooms with private toilet facilities.