For shared hosting, I have had good experiences with a2hosting, but hosting Elgg on a shared hosting is a bad idea and it won't scale well. I only use it to host demos.

I only know hostupon.com by own experience. I don't know if you are looking for a shared-server hosting (as you don't mention it explicitely while Ismayil refers to it). I also can't recommend any shared-server hosting plan. Sooner or later you will have issues (either direct performance issues on your site or the hoster will put your site offline because it caused problem for other sites on the same server). With hostupon I had started with a shared-server plan but soon had to move to a VPS plan. As it's managed hosting it's not cheap but apart from the problems I had at the beginning due to the shared hosting I'm satisfied with them. The initial server setup (years ago when I had not much experience yet) was done by them and the support reacts fast and helpful if there's any issues (not that there were any that really mattered).

I've tested Elgg on a $10/mo, 2GB RAM VPS few days ago. It works great. I've posted installation instructions on my blog if you're interested.

How to Install Elgg on Ubuntu VPS.

It's a video tutorial. Hope it helps.