Here's what I think.
Yes you can use Based on what or Based on at the beginning of a sentence.
Based on what he said, I decided not to go to the party.
Based on my experience, I have found it's best to ask a doctor for medical advice.
However I think there is a grammatical problem here when trying to use this construction with a question form. It's hard to pin it down though, however native English speakers will experinece these as being "odd" or "strange", somehow incomplete.
The problem here is with the order of the verbs. The auxiliary verb "do/did", as in "do/did you", is used in an inverted form which we use to form questions, but after that we expect there to be a main verb which should technically be "base" in your examples. However, you have put the main verb at the beginning of the question, when it should be after "you". Then what follows after that should be a noun or a noun phrase.
Here's how I would attempt to fix them, by changing the structure.
On what empirical evidenced did you base your statement?
On what order did you base the sequence of songs on the album?
On what information did you base your belief that I was lying?
*Note: These are quite formal, and I think No. 2 might just be too formal for this subject/context. It might be better to change this completely, something simpler perhaps, a more direct question.
How did you choose the order of the songs on the album?