To sum this all up, the breadboard is almost certainly the issue. The part in question need a tight layout, and requires a thermal sink for it's heat dissipation (see figure below with layout considerations from datasheet) Also, the extra capacitance and resistance of breadboard contacts is likely to cause issues, especially with the feedback loop.
1. Keep the input switching current loop as small as possible.
2. Keep the SW node as physically small and short as possible to minimize parasitic capacitance and
inductance and to minimize radiated emissions. Kelvin connections should be brought from the output to the
feedback pin of the device.
3. Keep analog and non-switching components away from switching components.
4. Make a single point connection from the signal ground to power ground.
5. Do not allow switching current to flow under the device.
6. Keep the pattern lines for VIN and PGND broad.
7. Exposed pad of device must be connected to PGND with solder.
8. VREG5 capacitor should be placed near the device, and connected PGND.
9. Output capacitor should be connected to a broad pattern of the PGND.
10. Voltage feedback loop should be as short as possible, and preferably with ground shield.
11. Lower resistor of the voltage divider which is connected to the VFB pin should be tied to SGND.
12. Providing sufficient via is preferable for VIN, SW and PGND connection.
13. PCB pattern for VIN, SW, and PGND should be as broad as possible.
14. VIN Capacitor should be placed as near as possible to the device.