I suggest asking the relocation agent specially what is included in your package and ensuring you get what's due. You should also have received a summary of the included benefits along with your offer package from your new employer.
I have seen temporary accommodation being extended by 1-2 months or extra accompanied visits being agreed (at additional cost) in these situations - check with your manager or HR contact if there is some flexibility in case you don't find something in time.
Have you asked your new employer if they have an internal marketplace that lists available apartments or if they have any employees who might be leaving soon and giving up their place?